oj.uz

Submission #360082

# Submission time Handle Problem Language Result Execution time Memory
360082 2021-01-27T12:45:14 Z Mlxa DEL13 (info1cup18_del13) C++14
30 / 100
 500 ms 7880 KB 
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e5 + 10;
int dp[N][3];

struct group {
	int l;
	int r;
	int k;
	group(int a, int b) : l(a), r(b), k(b - a + 1) {}
};

vector<group> g;

vector<int> sub(vector<int> a) {
	// cout << "sub" << endl;
	// for (int e : a) {
	// 	cout << e;
	// }
	// cout << endl << endl;

	int n = (int)a.size();
	fill_n(dp[0], 3 * N, -1);
	int i = 0;
	g.clear();
	while (i < n) {
		if (!a[i]) {
			++i;
			continue;
		}
		int l = i;
		while (i + 1 < n && a[i + 1]) {
			++i;
		}
		g.emplace_back(l, i);
		++i;
	}
	assert(g.size());
	int m = (int)g.size();

	// cout << "m = " << m << endl;
	// for (auto e : g) {
	// 	cout << e.l + 1 << " " << e.r + 1 << endl;
	// }
	// cout << "---" << endl;

	for (int least = 1; least <= 2; ++least) {
		int take = g[0].k - least;
		if (take < 0 || take % 2) {
			continue;
		}
		dp[0][least] = take / 2;
	}
	for (i = 1; i < m; ++i) {
		for (int pr = 0; pr <= 2 && pr <= g[i].k; ++pr) {
			if (dp[i - 1][pr] == -1) {
				continue;
			}
			int fw = g[i].k - pr;
			if (!fw) {
				fw = 0;
			} else if (fw % 2) {
				fw = 1;
			} else {
				fw = 2;
			}
			int take = g[i].k - pr - fw;
			// assert(take % 2 == 0);
			dp[i][fw] = take / 2;

			if (pr > 0 && fw == 2) {
				fw = 0;
				take = g[i].k - pr - fw;
				// assert(take % 2 == 0);
				dp[i][fw] = take / 2;
			}
		}
	}
	vector<pair<int, int>> num;
	for (i = 0; i < n; ++i) {
		num.emplace_back(i, a[i]);
	}

	i = m - 1;
	int j = 0;
	if (dp[i][j] == -1) {
		return {};
	}
	vector<int> local;
	
	vector<int> byg;
	while (i >= 0) {
		byg.push_back(dp[i][j]);
		j = g[i].k - j - 2 * dp[i][j];
		--i;
		// assert(0 <= j && j < 3);
	}
	reverse(all(byg));
	// assert((int)byg.size() == m);
	for (i = 0; i < m; ++i) {
		while (byg[i]--) {
			auto it = lower_bound(all(num), mp(g[i].l, -1LL));
			// assert(it < num.end() && it->x <= g[i].r && it->y == 1);
			auto nx = it + 1;
			// assert(nx < num.end() && nx->x <= g[i].r && nx->y == 1);
			auto nnx = nx + 1;
			// assert(nnx < num.end() && nnx->x <= g[i].r && nnx->y == 1);
			local.push_back(nx->x);
			num.erase(nnx);
			num.erase(it);
		}
	}
	while (num.size()) {
		int cnt = 0;
		while (num.size() && num.back().y) {
			++cnt;
			num.pop_back();
		}
		// assert(num.size() && num.back().y == 0);
		int mid = num.back().x;
		num.pop_back();
		while (cnt--) {
			local.push_back(mid);
			// assert(num.size() && num.back().y == 1);
			num.pop_back();
		}
	}
	return local;
}

vector<int> a, answer;

bool segment(int l, int r) {
	assert(0 <= l && l <= r && r < (int)a.size());
	vector<int> cur(a.begin() + l, a.begin() + r + 1);
	if (!count(all(cur), 1)) {
		return true;
	}
	vector<int> tmp = sub(cur);
	if (!tmp.size()) {
		return false;
	}
	for (int e : tmp) {
		answer.push_back(e + l + 1);
	}
	return true;
}

vector<int> checker(int n, vector<int> moves) {
	vector<int> arr(n, 0);
	for (int x : moves) {
		--x;
		assert(arr[x] == 0);
		int l = x - 1, r = x + 1;
		while (l >= 0 && arr[l] == 1) {
			--l;
		}
		while (r < n && arr[r] == 1) {
			++r;
		}
		assert(0 <= l && r < n);
		arr[l] = 1;
		arr[r] = 1;
	}
	return arr;
}

void solve() {
	int n, q;
	cin >> n >> q;
	a.assign(n, 1);
	for (int x; q--; ) {
		cin >> x;
		--x;
		a[x] = 0;
	}
	answer.clear();
	int to = n - 1;
	for (int from = n - 3; from >= 0; --from) {
		if (from + 1 < (int)a.size() && from + 2 <= to && !a[from] && !a[from + 1]) {
			if (!segment(from + 2, to)) {
				cout << "-1\n";
				return;
			}
			to = from - 1;
		}
	}
	if (0 <= to && !segment(0, to)) {
		cout << "-1\n";
		return;
	}
	// assert(checker(n, answer) == a);
	cout << answer.size() << "\n";
	for (int e : answer) {
		cout << e << " ";
	}
	cout << "\n";
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
	// assert(freopen("output.txt", "w", stdout));
#endif
	ios::sync_with_stdio(0); cin.tie(0);

	int tn;
	cin >> tn;
	while (tn--) {
		solve();
	}

	// int n;
	// cin >> n;
	// a.resize(n);
	// for (int &e : a) {
	// 	cin >> e;
	// }
	// auto e = sub(a);
	// cout << e.size() << endl;
	// for (int elem : e) {
	// 	cout << elem + 1 << " ";
	// }
	// cout << endl;

	cerr << 1000 * clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2668 KB Output is correct
2 Correct 94 ms 2668 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2668 KB Output is correct
2 Correct 94 ms 2668 KB Output is correct
3 Execution timed out 578 ms 2804 KB Time limit exceeded
4 Execution timed out 572 ms 2752 KB Time limit exceeded

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 3432 KB Output is correct
2 Correct 43 ms 7880 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2668 KB Output is correct
2 Correct 94 ms 2668 KB Output is correct
3 Execution timed out 578 ms 2804 KB Time limit exceeded
4 Execution timed out 572 ms 2752 KB Time limit exceeded
5 Correct 71 ms 2756 KB Output is correct
6 Correct 51 ms 2668 KB Output is correct
7 Correct 60 ms 2796 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2668 KB Output is correct
2 Correct 94 ms 2668 KB Output is correct
3 Execution timed out 578 ms 2804 KB Time limit exceeded
4 Execution timed out 572 ms 2752 KB Time limit exceeded
5 Correct 71 ms 2756 KB Output is correct
6 Correct 51 ms 2668 KB Output is correct
7 Correct 60 ms 2796 KB Output is correct
8 Execution timed out 1086 ms 7164 KB Time limit exceeded
9 Execution timed out 775 ms 7308 KB Time limit exceeded
10 Execution timed out 656 ms 7148 KB Time limit exceeded
11 Execution timed out 1032 ms 7144 KB Time limit exceeded