Submission #379200

#	Time	Username	Problem	Language	Result	Execution time	Memory
379200		cheissmart	Nice sequence (IZhO18_sequence)	C++14	100 / 100	513 ms	35024 KiB

sequence

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void solve() {
	int n, m;
	cin >> n >> m;
	int l = n + m - __gcd(n, m) - 1;
	vi in(l + 1), p(l + 1);
	for(int i = 0; i <= l; i++) {
		// i ---> i + m
		// i - n <--- i
		if(i + m <= l) in[i + m]++;
		if(i - n >= 0) in[i - n]++;
	}
	vi q;
	for(int i = 0; i <= l; i++) if(in[i] == 0) q.PB(i);
	for(int i = 0; i < int(q.size()); i++) {
		p[q[i]] = i;
		if(q[i] + m <= l) {
		in[q[i] + m]--;
			if(in[q[i] + m] == 0) q.PB(q[i] + m);
		}
		if(q[i] - n >= 0) {
			in[q[i] - n]--;
			if(in[q[i] - n] == 0) q.PB(q[i] - n);
		}
	}
	cout << l << '\n';
	for(int i = 1; i <= l; i++) {
		cout << p[i] - p[i - 1] << ' ';
	}
	cout << '\n';
}

signed main()
{
	IO_OP;

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