• 欢迎光临~

# AGC005D 做题体验

#### 判定可行解

(c_i=c_j) 时，我们连一条 ((i,j)) 双向边，代表第 (i) 位和第 (j) 位的数字应是相同的。

#### (p = 0)

[B={A_1+1,A_2,A_3,cdots,A_{m-1},A_m-1} ]

#### (p=1) 和 (p=2)

(p=1) 时，我们可以把奇数的元素 (A_{odd}) 放到 (A) 的最后一个位置。

``````#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('n')

const int N = 105;

int n, m, a[N], s, b[N];

signed main(void) {
std::cin >> n >> m;
for (int i = 1; i <= m; i++) std::cin >> a[i];
for (int i = 1; i <= m; i++) s += (a[i] & 1);
if (s > 2) {
std::cout << "Impossible" << std::endl;
return 0;
}
if (m == 1) {
std::cout << a[1] << std::endl;
if (a[1] == 1) {
std::cout << 1 << std::endl << 1;
return 0;
}
std::cout << 2 << std::endl;
std::cout << 1 << " " << a[1] - 1 << std::endl;
} else if (s == 0) {
for (int i = 1; i <= m; i ++) std::cout << a[i], quad; Enter;
a[1] ++; a[m] --;
if (a[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << a[i], quad;
Enter;
} else if (s == 1) {
std::stable_sort(a + 1, a + 1 + m, [](int p, int q) {return p % 2 < q % 2;});
for (int i = 1; i <= m; i++) std::cout << a[i], quad; Enter;
a[1] ++; a[m] --;
if (a[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << a[i], quad;
Enter;
} else {
int first = -1, last = -1;
for (int i = 1; i <= m; i++) {
if (a[i] % 2 == 0) continue;
if (first == -1) first = a[i];
else {last = a[i]; break;}
}
int tot = 1;
b[1] = first;
for (int i = 1; i <= m; i++)
if (a[i] % 2 == 0) b[++tot] = a[i];
b[++tot] = last;
for (int i = 1; i <= m; i++) std::cout << b[i], quad; Enter;
b[1] ++; b[m] --;
if (b[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << b[i], quad;
}
return 0;
}
``````