Submission #528531

#	Time	Username	Problem	Language	Result	Execution time	Memory
528531		new_acc	The Big Prize (IOI17_prize)	C++14	90 / 100	83 ms	1984 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;
    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;
    	int ind=0,p=500;
    	int maxi=0;
    	if(p*p!=n) p++;
    	for(int i=0;i<=min(n,p);i++){
    		vi a=que(i);
    		maxi=max(maxi,a[0]+a[1]);
    		t[i]=a[0]+a[1];
    		if(t[i]==0) return i;
    	}
    	while(ind<n-1){
    		s.insert(ind);
    		if(t[ind]==maxi) {p=t[ind];break;}
    		ind++,l++;
    	}	
    	auto it=s.end();
    	it--;
    	s.insert(n);
    	while(*it!=n){
    		auto it2=it;
    		it2++;
    		ile=0;
    		int k=*it2-1;
    		vi akt=que(k);
    		while(k>=*it+1 and akt[0]+akt[1]!=maxi){
    			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;
    }

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