Submission #528519

#	Time	Username	Problem	Language	Result	Execution time	Memory
528519		new_acc	The Big Prize (IOI17_prize)	C++14	0 / 100	109 ms	1064 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define fi first
#define se second
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
int t[N];
int t2[N][2];
set<int>s;
int n,ile;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vi que(int a){
	if(t2[a][0]){
		vi akt;
		akt.push_back(t2[a][0]),akt.push_back(t2[a][1]);
		return akt;
	}
	vi akt=ask(a);
	t2[a][0]=akt[0],t2[a][1]=akt[1];
	return akt;
}
int bs(int pocz,int kon,int x,int l){
	int sr;
	while(pocz<=kon){
		sr=(pocz+kon)/2;
		vi a=que(sr);
		ile++;
		if(a[0]+a[1]==0) return -(sr+1);
		if(a[0]+a[1]!=x) return sr;
		if(a[0]>l) kon=sr-1;
		else pocz=sr+1;
	}	
	return INT_MAX;
}
int find_best(int m){
	n=m;	
	int l=0,p;
	int ind;
	for(int i=1;i<=50;i++){
		int a=uniform_int_distribution<int>(1,n)(rng);
		vi akt=que(a);
		p=max(p,akt[0]+akt[1]);
	}
	s.insert(-1);
	auto it=s.begin();
	s.insert(n);
	while(*it!=n){
		auto it2=it;
		it2++;
		ile=0;
		if(*it+1==*it2){
			l++,it++;
			continue;
		}
		int k=*it2-1;
		vi akt=que(k);
		while(k>=*it+1 and akt[0]+akt[1]!=p){
			if(akt[0]+akt[1]==0) return k;
			s.insert(k),k--,akt=que(k);
		}
		if(k>=*it+1){
			vi akt=que(k);
			if(akt[0]+akt[1]==0) return k;
			if(akt[0]==l){
				l++,it++;
				continue;
			}
		}else {l++,it++;continue;}
		int pom=bs(*it+1,k,p,l);
		if(pom!=INT_MAX){
			if(pom<0) return abs(pom)-1;
			s.insert(pom);
		}
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:6: warning: unused variable 'ind' [-Wunused-variable]
   41 |  int ind;
      |      ^~~
prize.cpp:40:10: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |  int l=0,p;
      |          ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80