제출 #1057292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057292		shenfe1	커다란 상품 (IOI17_prize)	C++17	20 / 100	27 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=1000;
    int r=0;
    for(int i=0;i<L;i++){
        int j=rng()%n;
        cntMx=max(cntMx,sum(j));
        if(sum(j)==0)return j;
        if((n-sum(j))*1ll*(n-sum(j))+1>n)break;
        r=i;
    }
    // cout<<r+1<<"\n";
    queue<pair<pii,pii>>  q;
    q.push({{0,n-1},{cntMx,0}});
    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+R!=c){
        //     cout<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
        // }
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:9: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   41 |     int r=0;
      |         ^

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