Submission #386847

#	Time	Username	Problem	Language	Result	Execution time	Memory
386847		vanic	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2082 ms	81900 KiB

sequence

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
 
using namespace std;
 
const int maxn=1e6+5;
 
int n, m;
bool bio[maxn];
bool put[maxn];
int sz;
 
bool siri(int x){
	bio[x]=1;
	put[x]=1;
//	cout << x << endl;
	if(x+m<sz){
		if(put[x+m]){
			return 1;
		}
		if(!bio[x+m]){
			if(siri(x+m)){
				return 1;
			}
		}
	}
	if(x-n>-1){
		if(put[x-n]){
			return 1;
		}
		if(!bio[x-n]){
			if(siri(x-n)){
				return 1;
			}
		}
	}
	put[x]=0;
	return 0;
}
 
bool provjeri(int x){
	sz=x+1;
	for(int i=0; i<sz; i++){
		bio[i]=0;
		put[i]=0;
	}
	for(int i=0; i<sz; i++){
		if(!bio[i]){
			if(siri(i)){
				return 0;
			}
		}
	}
	return 1;
}

int binary(){
	int lo=0, hi=1e6, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(provjeri(mid)){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

vector < int > ms[maxn];
vector < int > top;

void dodaj(int x){
	bio[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!bio[ms[x][i]]){
			dodaj(ms[x][i]);
		}
	}
	top.push_back(x);
}

int val[maxn];

void rijesi(int x){
	sz=x+1;
	for(int i=0; i<sz; i++){
		bio[i]=0;
		if(i>=n){
			ms[i-n].push_back(i);
		}
		if(i>=m){
			ms[i].push_back(i-m);
		}
	}
	for(int i=0; i<sz; i++){
		if(!bio[i]){
			dodaj(i);
		}
	}
	for(int i=0; i<sz; i++){
//		cout << top[i] << ' ';
		val[top[i]]=i;
	}
//	cout << endl;
	top.clear();
	ms[0].clear();
	for(int i=1; i<sz; i++){
		ms[i].clear();
		cout << val[i]-val[i-1] << ' ';
	}
	cout << '\n';
}

void solve(){
	cin >> n >> m;
	int sol=binary();
	cout << sol << '\n';
	rijesi(sol);
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		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: 0 / 24