Submission #1246203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246203		StefanSebez	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	6012 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),Solve(mid+1,r);
    }
    else{
        int levo=odgovor[mid][0]-bt.Get(l-1);
        if(levo) Solve(l,mid-1);
        int desno=odgovor[mid][1]-bt.Get(r+1,N);
        if(desno) Solve(mid+1,r);
    }
}
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);
	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