Submission #426812

#	Time	Username	Problem	Language	Result	Execution time	Memory
426812		A_D	The Big Prize (IOI17_prize)	C++14	0 / 100	160 ms	7376 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
vector<int> vec[NN];
int bit[NN];
int seg[4*NN];
void build(int p,int s,int e)
{
    if(s==e){
        seg[p]=1;
        return;
    }
    build(p*2,s,(s+e)/2);
    build(p*2+1,(s+e)/2+1,e);
    seg[p]=seg[p*2]+seg[p*2+1];
}
int get3(int p,int s,int e,int tar)
{
    if(s==e){
        return s;
    }
//    cout<<s<<" "<<e<<" "<<tar<<" "<<seg[p*2]<<endl;
    if(seg[p*2]>=tar){
        return get3(p*2,s,(s+e)/2,tar);
    }
    else{
        return get3(p*2+1,(s+e)/2+1,e,tar-seg[p*2]);
    }
}
void update(int p,int s,int e,int i)
{
    if(s==e){
        seg[p]=0;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update(p*2,s,mid,i);
    }
    else{
        update(p*2+1,mid+1,e,i);
    }
    seg[p]=seg[p*2]+seg[p*2+1];
}
void add(int idx)
{
    while(idx<NN){
        bit[idx]++;
        idx+=(idx&-idx);
    }
}
int get(int idx)
{
    int ret=0;
    while(idx>0){
        ret+=bit[idx];
        idx-=(idx&-idx);
    }
    return ret;
}
int find_best(int n){
    int sq=sqrt(n);
    build(1,0,n-1);
    while(1){
        int l=0,r=n-1;
        while(l<=r){
            int mid=get3(1,0,n-1,(seg[1]+1)/2);
            if(vec[mid].empty()){
                vec[mid]=ask(mid);
            }
            int h=vec[mid][0]+vec[mid][1];
//            cout<<mid<<" "<<vec[mid][0]<<" "<<vec[mid][1]<<endl;
            if(h==0)return mid;
            if(h<=450){
                update(1,0,n-1,mid);
                add(mid+2);
                break;
            }
            if(vec[mid][0]-get(mid+2)){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
    }
    assert(0);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:63:9: warning: unused variable 'sq' [-Wunused-variable]
   63 |     int sq=sqrt(n);
      |         ^~

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