Submission #40511

#	Time	Username	Problem	Language	Result	Execution time	Memory
40511		szawinis	Nice sequence (IZhO18_sequence)	C++14	100 / 100	698 ms	41540 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+1;

int n, m, dsu[N], nxt[N], pos[N], res[N];
bool mark[N];

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	nxt[u] = v;
	mark[v] = true;
	u = root(u), v = root(v);
	assert(u != v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}

void solve() {
	scanf("%d %d", &n, &m);
	fill(dsu, dsu+N, -1);
	fill(nxt, nxt+N, -1);
	fill(pos, pos+N, -1);
	fill(mark, mark+N, 0);
	fill(res, res+N, 0);
	int k = 0;
	for(k = 1; k <= 2*max(n, m); k++) {
		// cout << k - n << ' ' << k << ' ' << endl;
		// cout << k << ' ' << k - m << endl;

		if(k - n >= 0 && k - m >= 0) {
			if(root(k - n) == root(k - m) || root(k) == root(k - n) || root(k) == root(k - m)) break;
			merge(k - n, k);
			merge(k, k - m);
		} else if(k - n >= 0) {
			if(root(k) == root(k - n)) break;
			merge(k - n, k);
		} else if(k - m >= 0) {
			if(root(k) == root(k - m)) break;
			merge(k, k - m);
		}
	}
	--k;
	vector<int> ord;
	for(int i = 0; i <= k; i++) if(!mark[i]) {
		ord.push_back(i);
		for(int j = ord.back(); nxt[j] != -1; j = nxt[j]) ord.push_back(nxt[j]);
		mark[i] = true;
	}

	// for(int i = 0; i <= k; i++) cout << nxt[i] << ' ';
	// cout << endl << endl;
	// assert(ord.size() == k+1);

	for(int i = 0; i <= k; i++) pos[ord[i]] = i;
	for(int i = 1; i <= k; i++) res[i] = pos[i-1] - pos[i];
	printf("%d\n", k);
	for(int i = 1; i <= k; i++) printf("%d ", res[i]);
	printf("\n");
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--) solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
sequence.cpp: In function 'int main()':
sequence.cpp:63:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
                 ^

• 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: 24 / 24