Submission #1057298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057298		shenfe1	The Big Prize (IOI17_prize)	C++17	97.41 / 100	28 ms	2392 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
    
using namespace std;
    
#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()
    
const int MAX=2e5+10;
    
bool use[MAX];
pii res[MAX];
    
pii cnt(int pos){
    if(use[pos])return res[pos];
    use[pos]=1;
    vector<int> v=ask(pos);
    return res[pos]={v[0],v[1]};
}
    
int sum(int pos){
    pii c=cnt(pos);
    return c.F+c.S;
}
    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}
    
int cntMx;
    
int find_best(int n){
    cntMx=0;
    int L=500;
    int r=0;
    for(int j=0;j<min(n,L);j++){
        cntMx=max(cntMx,sum(j));
        r++;
        if(sum(j)==0)return j;
        if(cntMx>n/2)break;
    }
    int pref=0;
    for(int j=0;j<r;j++){
        if(sum(j)!=cntMx)pref++;
    }
    queue<pair<pii,pii>>  q;
    q.push({{r,n-1},{cntMx,pref}});
    while(!q.empty()){
        int l=q.front().F.F,r=q.front().F.S,c=q.front().S.F,pl=q.front().S.S;
        q.pop();
        if(c==0)continue;
        if(c==r-l+1){
            for(int i=l;i<=r;i++){
                if(sum(i)==0)return i;
            }
            continue;
        }
        int tl=(l+r)/2,tr=(l+r)/2;
        while(tl>=l&&sum(tl)!=cntMx){
            if(sum(tl)==0)return tl;
            tl--;
        }
        while(tr<=r&&sum(tr)!=cntMx){
            if(sum(tr)==0)return tr;
            tr++;
        }
        int L=cnt(tl).F-pl;
        int R=c-L-max(0,tr-tl-1);
        if(l<=tl-1)q.push({{l,tl-1},{L,pl}});
        if(tr+1<=r)q.push({{tr+1,r},{R,cnt(tr).F}});
    }
    return -1;
}

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