Submission #701676

#	Time	Username	Problem	Language	Result	Execution time	Memory
701676		angelo_torres	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1203 ms	84624 KiB

sequence

#include <bits/stdc++.h>
#define sz(v) (ll) v.size()
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll N = 6e5 + 20;

ll sum(ll a,ll b){ return (a+b)%mod; }
ll mul(ll a,ll b){ return (a*b)%mod; }
ll res(ll a,ll b){ return (a-b+mod)%mod; }

int n,m,r[N];
vector<int> g[N];
bool c = 0;

void dfs(int v){
	r[v] = 1;
	for(auto u : g[v]){
		if(r[u] == 1) c = 1;
		if(!r[u]) dfs(u);
	}
	r[v] = 2;
}

bool go(int k){
	c = 0;
	for(int i = 0; i <= k; ++i){
		g[i].clear();
		r[i] = 0;
	} 
	for(int i = 0; i+n <= k; ++i){
		g[i].push_back(i+n);
	}
	for(int i = 0; i+m <= k; ++i){
		g[i+m].push_back(i);
	}
	for(int i = 0; i <= k; ++i){
		if(!r[i]) dfs(i);
	} 
	return c;
}

vector<ll> t;

void top(int v){
	r[v] = 1;
	for(auto u : g[v]){
		if(!r[u]) top(u);
	}
	t.push_back(v);
}

void solve(){
	cin >> n >> m;
	bool fl = (n < m);
	if(n > m) swap(n,m);
	// int L = 0, R = n+m-gcd(n,m)+2;
	// while(R-L > 1){
	// 	int md = (L+R)>>1;
	// 	if(go(md)) R = md;
	// 	else L = md;
	// }
	int L = n+m-gcd(n,m)-1;
	cout << L << endl;
	t.clear();
	for(int i  = 0; i <= L; ++i){
		g[i].clear();
		r[i] = 0; 
	} 
	for(int i = 0; i+n <= L; ++i){
		g[i].push_back(i+n);
	}
	for(int i = 0; i+m <= L; ++i){
		g[i+m].push_back(i);
	}
	for(int i = 0; i <= L; ++i){
		if(!r[i]) top(i);
	}
	vector<int> p(L+1);
	for(int i = 0; i <= L; ++i){
		p[t[i]] = i;
	}
	for(int i = 0; i+1 <= L; ++i){
		int ai = p[i+1]-p[i];
		cout << (fl ? ai : -ai) << " "; 
	}
	cout << endl;
}


int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test; cin >> test;
	while(test--) solve();
	return 0;
}

• 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