oj.uz

Submission #1057266

# Submission time Handle Problem Language Result Execution time Memory
1057266 2024-08-13T16:07:09 Z shenfe1 The Big Prize (IOI17_prize) C++17
0 / 100
 3 ms 4720 KB 
#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];
int cq;

pii cnt(int pos){
    if(use[pos])return res[pos];
    use[pos]=1;
    cq++;
    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());

struct segtree{
    int t[4*MAX];
 
    segtree(){
        memset(t,0,sizeof(t));
    }
 
    void update(int v,int tl,int tr,int pos){
        if(tl==tr){
            t[v]=1;
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm)update(2*v,tl,tm,pos);
        else update(2*v+1,tm+1,tr,pos);
        t[v]=t[2*v]+t[2*v+1];
    }
 
    int get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return 0;
        if(l<=tl&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r);
    }
}T;

int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}

int cntMx;

int find_best(int n){
    int init=cq;
    cntMx=0;
    for(int j=0;j<min(n,450);j++){
        cntMx=max(cntMx,sum(j));
        if(sum(j)==0)return j;
    }
    int pref=0;
    for(int j=0;j<min(n,450);j++){
        cntMx=max(cntMx,sum(j));
        if(sum(j)!=cntMx)pref++;
    }
    queue<pair<pii,pii>>  q;
    q.push({{450,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;
        }
        // cerr<<l<<" "<<r<<"\n";
        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-1).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(tl-1).F+max(0,tr-tl-1)}});
    }
    return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:67:9: warning: unused variable 'init' [-Wunused-variable]
   67 |     int init=cq;
      |         ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Incorrect 3 ms 4696 KB Integer -1 violates the range [0, 199999]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Incorrect 3 ms 4720 KB Integer -1 violates the range [0, 199999]
3 Halted 0 ms 0 KB -