제출 #302184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302184		dantoh000	커다란 상품 (IOI17_prize)	C++14	97.60 / 100	64 ms	488 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int mx = 0;
int ans = -1;
void search(int ll, int lr, int rl, int rr, int cl, int cr, int c);
void search(int L, int R, int cl, int cr, int c){
    if (ans != -1 || c == 0) return;
    //printf("searching %d %d %d %d %d\n",L,R,cl,cr,c);
     if (L == R){
        vector<int> p = ask(L);
        if (p[0] + p[1] == 0) ans = L;
        return;
    }
    if (L > R) return;
    int mid = (L+R)/2;
    //printf("mid %d\n",mid);
    search(L, mid, mid+1, R, cl, cr, c);
    return;
}
void search(int ll, int lr, int rl, int rr, int cl, int cr, int c){
    if (ans != -1 || c == 0) return;
    //printf("search <%d,%d><%d,%d>, <%d,%d>, %d\n",ll,lr,rl,rr,cl,cr,c);
    if (ll == rr){
        search(ll, rr, cl, cr, c);
        return;
    }
    int CL, CR;
    int q = (rr-rl)>(lr-ll)?rl:lr;
    vector<int> p = ask(q);
    CL = p[0], CR = p[1];
    //printf("queried %d, got (%d,%d)\n",q,CL,CR);
    if (CL + CR != mx){ /// is special
        if (CL + CR == 0){
            ans = q;
            return;
        }
        //printf("add pos %d\n",q);
       // printf("check: %d\n",g[q]);
        if (q == lr){
            if (ll <= lr-1) search(ll, lr-1, rl, rr, cl, cr, c-1);
            else search(rl, rr, cl+1, cr, c-1);

        }
        else if (q == rl){
            if (rl+1 <= rr) search(ll, lr, rl+1, rr, cl, cr, c-1);
            else search(ll, lr, cl, cr+1, c-1);
        }
        return;
    }
    CR -= cr;
    CL -= cl;
    if (q == lr){
        if (ll <= lr-1) search(ll, lr-1,cl,CR+cr,CL);
        search(rl, rr,CL+cl,cr,CR);
    }
    else{
        search(ll, lr,cl,CR+cr,CL);
        if (rl+1 <= rr) search(rl+1, rr,CL+cl,cr,CR);
    }
}
int find_best(int n) {
    int ct = 0;
    int num = 0;
    int hmm;
    for (hmm = 0; hmm < min(n,474); hmm++){
        vector<int> p = ask(hmm);
        if (p[0] == 0 && p[1] == 0) return hmm;
        if (mx < p[0]+p[1]){
            ct = hmm-1;
            mx = p[0]+p[1];
        }
        else if (p[0]+p[1] < mx) ct++;
    }
    search(hmm+1, n-1, ct, 0, mx-ct);
    //printf("output %d\n",ans);
    return ans;
}

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

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

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