oj.uz

답안 #360049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360049 2021-01-27T12:26:05 Z Mlxa DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 28988 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));
#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;

	return 0;
}

Subtask #1
0.0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1041 ms 23788 KB Time limit exceeded
2 Execution timed out 1083 ms 23832 KB Time limit exceeded
3 Execution timed out 1097 ms 23916 KB Time limit exceeded
4 Execution timed out 1087 ms 23916 KB Time limit exceeded

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1052 ms 24332 KB Time limit exceeded
2 Execution timed out 676 ms 28988 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1041 ms 23788 KB Time limit exceeded
2 Execution timed out 1083 ms 23832 KB Time limit exceeded
3 Execution timed out 1097 ms 23916 KB Time limit exceeded
4 Execution timed out 1087 ms 23916 KB Time limit exceeded
5 Execution timed out 1084 ms 23916 KB Time limit exceeded
6 Execution timed out 1025 ms 24048 KB Time limit exceeded
7 Execution timed out 1090 ms 23788 KB Time limit exceeded

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1041 ms 23788 KB Time limit exceeded
2 Execution timed out 1083 ms 23832 KB Time limit exceeded
3 Execution timed out 1097 ms 23916 KB Time limit exceeded
4 Execution timed out 1087 ms 23916 KB Time limit exceeded
5 Execution timed out 1084 ms 23916 KB Time limit exceeded
6 Execution timed out 1025 ms 24048 KB Time limit exceeded
7 Execution timed out 1090 ms 23788 KB Time limit exceeded
8 Execution timed out 1097 ms 24044 KB Time limit exceeded
9 Execution timed out 1085 ms 24300 KB Time limit exceeded
10 Execution timed out 1101 ms 28260 KB Time limit exceeded
11 Execution timed out 1089 ms 28268 KB Time limit exceeded