oj.uz

Submission #44827

# Submission time Handle Problem Language Result Execution time Memory
44827 2018-04-07T10:46:53 Z aome DEL13 (info1cup18_del13) C++17
100 / 100
 23 ms 1644 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

bool ok;
bool f[N][3];
vector<int> buf, res;

int F(int x) { 
	if (x == 0) return 0;
	if (x % 2 == 1) return 1;
	if (x % 2 == 0) return 2;
}

void calc(int pos) {
	if (buf.size() == 0) return;
	if (buf.size() == 1) { ok = 0; return; } 
	reverse(buf.begin(), buf.end());
	int sz = buf.size();
	vector<int> end;
	for (int i = 0; i < sz; ++i) {
		end.push_back(pos), pos -= buf[i] + 1;
	}
	f[0][0] = 1;
	for (int i = 1; i <= sz; ++i) {
		f[i][0] = f[i][1] = f[i][2] = 0;
	}
	for (int i = 0; i < sz; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (!f[i][j]) continue;
			if (buf[i] >= j) f[i + 1][F(buf[i] - j)] = 1;
			if (F(buf[i]) >= j) f[i + 1][F(buf[i]) - j] = 1;
		}
	}
	if (!f[sz][0]) { ok = 0; return; }
	int x = sz, y = 0;
	vector<int> tmp;
	while (x--) {
		for (int i = 0; i < 3; ++i) {
			if (!f[x][i]) continue;
			if (buf[x] >= i && F(buf[x] - i) == y) {
				y = i;
				int l = end[x] - buf[x] + 1, r = end[x];
				buf[x] -= i;
				while (buf[x] > 2) {
					tmp.push_back(l + 1), l += 2, buf[x] -= 2;
				}
				while (i--) tmp.push_back(r + 1);	
				break;
			} 
			if (F(buf[x]) >= i && F(buf[x]) - i == y) {
				y = i;
				int l = end[x] - buf[x] + 1, r = end[x];
				while (i--) tmp.push_back(r + 1);
				while (buf[x] > 2) {
					tmp.push_back(l + 1), l += 2, buf[x] -= 2;
				}
				break;
			}	
		}
	}
	reverse(tmp.begin(), tmp.end());
	for (auto i : tmp) res.push_back(i);
}

void solve() {
	int n, m;
	vector<int> a;
	cin >> n >> m;
	a.push_back(0);
	for (int i = 0; i < m; ++i) {
		int x; cin >> x, a.push_back(x);
	}
	a.push_back(n + 1);
	ok = 1, res.clear();
	for (int i = 1; i <= m + 1; ++i) {
		if (a[i] == a[i - 1] + 1) {
			calc(a[i - 1] - 1), buf.clear(); continue;
		}
		buf.push_back(a[i] - a[i - 1] - 1);
	}
	calc(n), buf.clear();
	if (!ok) {
		cout << "-1\n"; return;
	}
	cout << res.size() << '\n';
	for (auto i : res) cout << i << ' '; cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t; while (t--) solve();
}

Compilation message

del13.cpp: In function 'void solve()':
del13.cpp:89:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto i : res) cout << i << ' '; cout << '\n';
  ^~~
del13.cpp:89:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto i : res) cout << i << ' '; cout << '\n';
                                       ^~~~
del13.cpp: In function 'int F(int)':
del13.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 11 ms 688 KB Output is correct
4 Correct 12 ms 688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 796 KB Output is correct
2 Correct 4 ms 796 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 11 ms 688 KB Output is correct
4 Correct 12 ms 688 KB Output is correct
5 Correct 3 ms 796 KB Output is correct
6 Correct 3 ms 796 KB Output is correct
7 Correct 3 ms 796 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 11 ms 688 KB Output is correct
4 Correct 12 ms 688 KB Output is correct
5 Correct 3 ms 796 KB Output is correct
6 Correct 3 ms 796 KB Output is correct
7 Correct 3 ms 796 KB Output is correct
8 Correct 12 ms 796 KB Output is correct
9 Correct 12 ms 924 KB Output is correct
10 Correct 12 ms 1004 KB Output is correct
11 Correct 23 ms 1644 KB Output is correct