oj.uz

답안 #360068

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

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 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 512 KB Output isn't correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Incorrect 6 ms 364 KB Output isn't correct
4 Incorrect 7 ms 492 KB Output isn't correct

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 146 ms 824 KB Output isn't correct
2 Incorrect 8 ms 5576 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Incorrect 6 ms 364 KB Output isn't correct
4 Incorrect 7 ms 492 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 364 KB Output isn't correct

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Incorrect 6 ms 364 KB Output isn't correct
4 Incorrect 7 ms 492 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Runtime error 19 ms 4832 KB Execution killed with signal 11
9 Correct 14 ms 5060 KB Output is correct
10 Runtime error 14 ms 4716 KB Execution killed with signal 11
11 Execution timed out 1091 ms 4840 KB Time limit exceeded