oj.uz

답안 #360087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
360087 2021-01-27T12:48:41 Z Mlxa DEL13 (info1cup18_del13) C++14
100 / 100
 55 ms 11092 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;
			}
		}
	}
	set<pair<int, int>> nums;
	for (i = 0; i < n; ++i) {
		nums.emplace(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 =  nums.lower_bound(mp(g[i].l, -1LL));
			// assert(it < num.end() && it->x <= g[i].r && it->y == 1);
			auto nx = next(it);
			// assert(nx < num.end() && nx->x <= g[i].r && nx->y == 1);
			auto nnx = next(nx);
			// assert(nnx < num.end() && nnx->x <= g[i].r && nnx->y == 1);
			local.push_back(nx->x);
			nums.erase(nnx);
			nums.erase(it);
		}
	}
	while (nums.size()) {
		int cnt = 0;
		while (nums.size() && nums.rbegin()->y) {
			++cnt;
			nums.erase(*nums.rbegin());
		}
		// assert(num.size() && num.back().y == 0);
		int mid = nums.rbegin()->x;
		nums.erase(*nums.rbegin());
		while (cnt--) {
			local.push_back(mid);
			// assert(num.size() && num.back().y == 1);
			nums.erase(*nums.rbegin());
		}
	}
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1004 KB Output is correct
2 Correct 43 ms 9116 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 49 ms 10604 KB Output is correct
9 Correct 42 ms 11092 KB Output is correct
10 Correct 39 ms 10604 KB Output is correct
11 Correct 55 ms 10860 KB Output is correct