제출 #1136740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136740		sonamoo	커다란 상품 (IOI17_prize)	C++20	98.95 / 100	15 ms	6060 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define sz 473
#define SIZE 200005

using namespace std;

int chk[SIZE] , ma=-1;
vector<int> ret[SIZE];
vector<int> res;

vector<int> Ask(int p) {
    if (chk[p] == 1) return ret[p];
    chk[p] = 1;
    return ret[p] = ask(p);
}

int S[SIZE] , E[SIZE] , pv;

int f(int s , int e , int x) {
    int ans = 0;
    while(s <= e) {
        int m = (s+e)/2;
        if (Ask(m)[0]+Ask(m)[1] != ma) {
            ans = m;
            e = m-1;
        }
        else {
            if (Ask(m)[0] == x) s = m+1;
            else e = m-1;
        }
    }
    return ans;
}

int find_best(int n) {

    if (n <= 5000) {
        for (int i = 0; i < n; i++) {
            if (Ask(i)[0]+Ask(i)[1]==0) return i;
        }
        return 0;
    }

    for (int i = 0; i <= sz; i++) {
        ma = max(ma , Ask(i)[0]+Ask(i)[1]);
    }

    S[++pv]=0,E[pv]=0;
    for (int i = 1; i < n; i++) {
        if (E[pv]-S[pv]+1==sz) S[++pv]=i;
        E[pv]=i;
    }

    int g=1, cnt=0 , prv=-1;
    while(g <= pv) {
        if (prv >= E[g]) {
            g++; continue;
        }
        if (Ask(E[g])[0]+Ask(E[g])[1]==ma && Ask(E[g])[0]==cnt) {
            g++; continue;
        }
        int p = f(max(prv+1,S[g]) , E[g] , cnt);
        res.push_back(p);
        cnt++; prv=p;
    }

    for (auto t : res) if (Ask(t)[0]+Ask(t)[1]==0) return t;

    assert(1);
	return 0;
}

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