oj.uz

답안 #360062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360062 2021-01-27T12:32:18 Z Mlxa DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 29116 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 = 1e6 + 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;
}

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 << 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
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 23788 KB Time limit exceeded
2 Execution timed out 1084 ms 23788 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 23788 KB Time limit exceeded
2 Execution timed out 1084 ms 23788 KB Time limit exceeded
3 Execution timed out 1091 ms 23916 KB Time limit exceeded
4 Execution timed out 1052 ms 23916 KB Time limit exceeded

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1048 ms 24336 KB Time limit exceeded
2 Execution timed out 668 ms 29116 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 23788 KB Time limit exceeded
2 Execution timed out 1084 ms 23788 KB Time limit exceeded
3 Execution timed out 1091 ms 23916 KB Time limit exceeded
4 Execution timed out 1052 ms 23916 KB Time limit exceeded
5 Execution timed out 1097 ms 23916 KB Time limit exceeded
6 Execution timed out 1000 ms 23788 KB Time limit exceeded
7 Execution timed out 1099 ms 23916 KB Time limit exceeded

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 23788 KB Time limit exceeded
2 Execution timed out 1084 ms 23788 KB Time limit exceeded
3 Execution timed out 1091 ms 23916 KB Time limit exceeded
4 Execution timed out 1052 ms 23916 KB Time limit exceeded
5 Execution timed out 1097 ms 23916 KB Time limit exceeded
6 Execution timed out 1000 ms 23788 KB Time limit exceeded
7 Execution timed out 1099 ms 23916 KB Time limit exceeded
8 Execution timed out 1085 ms 24060 KB Time limit exceeded
9 Execution timed out 1087 ms 24044 KB Time limit exceeded
10 Execution timed out 1080 ms 28268 KB Time limit exceeded
11 Execution timed out 1069 ms 28264 KB Time limit exceeded