Submission #386756

#	Time	Username	Problem	Language	Result	Execution time	Memory
386756		vanic	Nice sequence (IZhO18_sequence)	C++14	0 / 100	18 ms	5228 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;
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;
	bio.reset();
	put.reset();
	for(int i=0; i<x; i++){
		if(!bio[i]){
			if(siri(i)){
				return 0;
			}
		}
	}
	return 1;
}

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

void solve(){
	cin >> n >> m;
	int sol=binary();
	cout << sol << '\n';
}

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: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24