Submission #41502

#	Time	Username	Problem	Language	Result	Execution time	Memory
41502		aome	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2053 ms	36028 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const int N = 400005;

vector<int> vec, res;
vector<int> G[N];
int vis[N];
int n, m;
bool ok;

void dfs(int u, bool trace) {
	vis[u] = 1;
	for (auto v : G[u]) {
		if (!vis[v]) dfs(v, trace);
		else ok &= vis[v] == 2;
	}
	vis[u] = 2;
	if (trace) vec.push_back(u); 
}

bool check(int x, bool trace) {
	for (int i = 0; i <= x; ++i) {
		G[i].clear(), vis[i] = 0;
	}
	// u -> v <-> S(u) < S(v)
	for (int i = n; i <= x; ++i) {
		G[i].push_back(i - n);
	}
	for (int i = m; i <= x; ++i) {
		G[i - m].push_back(i);
	}
	ok = 1;
	for (int i = 0; i <= x; ++i) {
		if (!vis[i]) dfs(i, trace);
	}
	return ok;
}

void solve() {
	cin >> n >> m;
	int l = 0, r = max(n, m) * 2;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (check(mid, 0)) l = mid;
		else r = mid - 1;
	}
	vec.clear(), check(l, 1);
	reverse(vec.begin(), vec.end());
	int len = vec.size(), pos0 = 0;
	for (int i = 0; i < len; ++i) if (!vec[i]) pos0 = i;
	res.assign(len, 0);
	for (int i = 0; i < len; ++i) {
		res[vec[i]] = i - pos0;
	}
	cout << len - 1 << '\n';
	for (int i = 1; i < len; ++i) cout << res[i] - res[i - 1] << ' '; cout << '\n';
}

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

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 0 / 24