Submission #1246225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246225		StefanSebez	The Big Prize (IOI17_prize)	C++20	20 / 100	1040 ms	7812 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;
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]);
    }
	//Solve(0,n-1);
	while(bt.Get(0,N)<MAKS){
        vector<int>ind;
        for(int i=0;i<n;i++) if(bt.Get(i,i)==0) ind.pb(i);
        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);
                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: 0 / 80