제출 #577472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577472		definitelynotmee	커다란 상품 (IOI17_prize)	C++98	100 / 100	65 ms	11336 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

vector<vector<int>> resp;

vector<int> query(int id){
    if(resp[id][0] == -1){
        resp[id] = ask(id);
    }
    return resp[id];
}

int find_best(int n) {
	resp = vector<vector<int>>(n,{-1,-1});
    vector<int> start = ask(0);
    int ct = start[0]+start[1];
    if(ct == 0)
        return 0;
    
    vector<int> cand;
    bool flag = 0;

    auto solve =[&](int l, int r, int discl, int discr, auto solve)->void{
        if(r < l)
            return;
        
        if(discl + discr == ct)
            return;
        int m = (l+r)>>1;
        int mid = m;

        vector<int> ret = query(m);

        while(m <= r && ret[0]+ret[1] < ct){
            cand.push_back(m);
            m++;
            if(m <= r)
                ret = query(m);
        }

        if(ret[0]+ret[1] > ct){
            ct = ret[0]+ret[1];
            flag = 1;
            return;
        }

        if(m > r){
            int m = mid-1;
            if(m < l)
                return;
            ret = query(m);
            while(m >= l && ret[0]+ret[1] < ct){
                cand.push_back(m);
                m--;
                if(m >= l)
                    ret = query(m);
            }
            solve(l,m-1,discl,ret[1],solve);
            return;
        }
        solve(l,mid-1,discl,ret[1]+m-mid,solve);
        solve(m+1,r,ret[0],discr,solve);
    };
    do{
        cand.clear();
        flag = 0;
        solve(0,n-1,0,0,solve);
    } while(flag);
    
    for(int i : cand){
        vector<int> ret = query(i);
        if(ret[0]+ret[1] == 0){
            return i;
        }
    }

}

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:24:30: warning: control reaches end of non-void function [-Wreturn-type]
   24 |     vector<int> start = ask(0);
      |                              ^

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