Submission #507939

#	Time	Username	Problem	Language	Result	Execution time	Memory
507939		Mazaalai	Nice sequence (IZhO18_sequence)	C++17	100 / 100	409 ms	51288 KiB

sequence

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
int n, m, mul, k, lim;
int arr[2*N], curVal;
bool vis[2*N], possible;
void solve(int pos) {
	if (arr[pos] != 0) return;
	if (vis[pos]) {
		possible = 0;
		return;
	}
	vis[pos] = 1;
	if (possible && pos+m <= lim) solve(pos+m);
	if (possible && pos-n >= 0) solve(pos-n);
	arr[pos] = curVal++;
}
int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b % a, a);
}
void go() {
	cin >> n >> m;
	vector <int> ans(1, 1);
	k = max(n, m);
	int l = k-1, r = n+m-1;
	l = r = n + m - 1 - gcd(n, m);
	while(l <= r) {
		int mid = (l+r)>>1;
		curVal = possible = 1;
		for (int i = 0; i < 2*k+5; i++) 
			arr[i] = vis[i] = 0;
		lim = mid;
		for (int i = 0; i <= mid && possible; i++) {
			if (vis[i]) continue;
			solve(i);
		}
		if (!possible) {
			r = mid-1;
		} else {
			l = mid+1;
			vector <int> cur;
			for (int i = 1; i <= mid; i++) cur.pb(arr[i] - arr[i-1]);
			ans = cur;
		}
	}
	cout << ans.size() << '\n';
	for (auto el : ans) cout << -el << ' '; cout << '\n';

}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	int T;
	cin >> T;
	while(T--) go();
}

Compilation message (stderr)

sequence.cpp: In function 'void go()':
sequence.cpp:49:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |  for (auto el : ans) cout << -el << ' '; cout << '\n';
      |  ^~~
sequence.cpp:49:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |  for (auto el : ans) cout << -el << ' '; cout << '\n';
      |                                          ^~~~

• 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