Submission #386856

#	Time	Username	Problem	Language	Result	Execution time	Memory
386856		vanic	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1661 ms	51500 KiB

sequence

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
 
using namespace std;
 
const int maxn=4e5+5;
 
int n, m;
bitset < maxn > bio;
bitset < maxn > put;
int sz;
 
bool siri(int x){
	bio[x]=1;
	put[x]=1;
	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;
	bio.reset();
	put.reset();
	for(int i=0; i<sz; i++){
		if(!bio[i]){
			if(siri(i)){
				return 0;
			}
		}
	}
	return 1;
}

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

vector < int > top;

void dodaj(int x){
	bio[x]=1;
	if(x+n<sz && !bio[x+n]){
		dodaj(x+n);
	}
	if(x-m>-1 && !bio[x-m]){
		dodaj(x-m);
	}
	top.push_back(x);
}

int val[maxn];

void rijesi(int x){
	sz=x+1;
	bio.reset();
	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();
	for(int i=1; i<sz; i++){
		printf("%d ", val[i]-val[i-1]);
	}
	printf("\n");
}

void solve(){
	scanf("%d%d", &n, &m);
	int sol=binary();
	printf("%d\n", sol);
	rijesi(sol);
}
 
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		solve();
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |  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