Submission #1246235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246235		StefanSebez	The Big Prize (IOI17_prize)	C++20	90 / 100	505 ms	8096 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
void ckmx(int &x,int y){x=max(x,y);}
void ckmn(int &x,int y){x=min(x,y);}
const int N=2e5+50,S=500;
vector<int>odgovor[N];
int MAKS;
bool mali[N];
struct BIT{
    int T[N+50];
    void Update(int i,int x){i+=10;for(;i<=N;i+=i&-i)T[i]+=x;}
    int Get(int i){i+=10;int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
    int Get(int l,int r){return Get(r)-Get(l-1);}
}bt;
/*void Solve(int l,int r){
    if(l>r) return;
    int mid=l+r>>1;
    odgovor[mid]=ask(mid);
    if(odgovor[mid][0]+odgovor[mid][1]!=MAKS){
        bt.Update(mid,1);
        Solve(l,mid-1);
    }
    else{
        int levo=odgovor[mid][0]-bt.Get(l-1);
        if(levo) Solve(l,mid-1);
    }

}*/
int find_best(int n){
    for(int i=0;i<min(S,n);i++){
        odgovor[i]=ask(i);
        ckmx(MAKS,odgovor[i][0]+odgovor[i][1]);
    }
    for(int i=0;i<n;i++){
        if(odgovor[i].empty()) continue;
        if(odgovor[i][0]+odgovor[i][1]<MAKS){
            bt.Update(i,1);
            mali[i]=1;
        }
    }
	//Solve(0,n-1);
	while(1){
        vector<int>ind;
        for(int i=0;i<n;i++) if(!mali[i]) ind.pb(i);
        if(n-ind.size()==MAKS) break;
        int l=0,r=ind.size()-1;
        while(l<=r){
            int mid=l+r>>1,j=ind[mid];
            odgovor[j]=ask(j);
            if(odgovor[j][0]+odgovor[j][1]!=MAKS){
                bt.Update(j,1);
                mali[j]=1;
                break;
            }
            if(odgovor[j][0]>bt.Get(j)){r=mid-1;}
            else l=mid+1;
        }
	}
	int res=0;
	for(int i=0;i<n;i++){
        if(odgovor[i].empty()) continue;
        if(odgovor[i][0]+odgovor[i][1]==0) res=i;
	}
	return res;
}

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