Submission #344353

#	Time	Username	Problem	Language	Result	Execution time	Memory
344353		79brue	커다란 상품 (IOI17_prize)	C++14	100 / 100	104 ms	7776 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

typedef long long ll;

struct dat{
    int l, r, lx, rx;
    dat(){}
    dat(int l, int r, int lx, int rx): l(l), r(r), lx(lx), rx(rx){}
};

vector<int> vec;
vector<int> chk[200002];
int connect[200002];
int queryCount;

vector<int> my_ask(int x){
    if(chk[x].size() == 2) return chk[x];
    queryCount++;
    return chk[x] = ask(x);
}

int find_best(int n){
    for(int i=1; i<=200000; i++){
        int tmp = int(floor(sqrt(i-1)) + 1e-8);
        connect[i] = connect[tmp] + i;
    }

    for(int i=0; i<n; i++) vec.push_back(i);
    while((int)vec.size() > 1){
        queue<dat> que;
        int k = (int)vec.size();

        int sum = 0, lim = 0;
        for(int i=0; connect[i+1] + (i+1)*(i+1) + 1 <= k; i++) lim = connect[i+1];
        vector<int> randomVec = vec;
        random_shuffle(randomVec.begin(), randomVec.end());
        sort(randomVec.begin(), randomVec.end(), [&](auto x, auto y){
            if(chk[x].size() == 2 && chk[y].size() != 2) return x<y;
            if(chk[x].size() != 2 && chk[y].size() == 2) return x>y;
            return false;
        });
        for(int i=0; i<=lim && i<k; i++){
            auto tVec = my_ask(randomVec[i]);
            sum = max(sum, tVec[0] + tVec[1]);
            if(sum >= lim) break;
        }
        que.push(dat(0, k-1, 0, 0));

        vector<int> newVec;

        while(!que.empty()){
            dat tmp = que.front(); que.pop();
            int cnt = tmp.r - tmp.l + 1 - (sum - tmp.lx - tmp.rx);
            if(cnt == 0){
                for(int x=tmp.l; x<=tmp.r; x++){
                    newVec.push_back(vec[x]);
                }
                continue;
            }

            int mid = (tmp.l + tmp.r) / 2;
            int midL = mid, midR = mid;
            while(mid <= tmp.r){
                auto tVec = my_ask(vec[mid]);
                if(tVec[0] + tVec[1] == sum) break;
                midR = mid;
                newVec.push_back(vec[mid++]);
            }
            if(mid > tmp.r){
                mid = (tmp.l + tmp.r) / 2;
                while(mid >= tmp.l){
                    auto tVec = my_ask(vec[mid]);
                    if(tVec[0] + tVec[1] == sum) break;
                    midL = mid;
                    newVec.push_back(vec[mid--]);
                }
            }
            if(mid < tmp.l) continue;

            auto tVec = my_ask(vec[mid]);
            assert(tVec[0] + tVec[1] == sum);
            if(tVec[0] != tmp.lx){
                int rightCount = tVec[1];
                if(mid == midR + 1) rightCount += (midR - (tmp.l + tmp.r) / 2 + 1);
                que.push(dat(tmp.l, midL-1, tmp.lx, rightCount));
            }
            if(midR+1 <= tmp.r && tVec[1] != tmp.rx) que.push(dat(midR+1, tmp.r, tVec[0], tmp.rx));
        }

        vec = newVec;
        sort(vec.begin(), vec.end());
    }
    return vec[0];
}

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