oj.uz

Submission #360081

# Submission time Handle Problem Language Result Execution time Memory
360081 2021-01-27T12:44:26 Z Mlxa DEL13 (info1cup18_del13) C++14
70 / 100
 500 ms 5576 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 = 15;
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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 7 ms 364 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 824 KB Output is correct
2 Correct 8 ms 5576 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Runtime error 20 ms 4832 KB Execution killed with signal 11
9 Correct 14 ms 5004 KB Output is correct
10 Runtime error 17 ms 4716 KB Execution killed with signal 11
11 Execution timed out 1089 ms 4840 KB Time limit exceeded