제출 #421155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421155		MarcoMeijer	커다란 상품 (IOI17_prize)	C++14	100 / 100	63 ms	956 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int big=0;
int n;

vi Ask(int i) {
    static map<int,vi> mem;
    auto it = mem.find(i);
    if(it != mem.end())
        return it->second;
    return mem[i] = ask(i);
}

int getSum(int i) {
    if(i < 0 || i >= n) return big;
    return Ask(i)[0] + Ask(i)[1];
}

int getBiggestSize(int lb, int ub, int dep=9) {
    if(dep == 0) return 0;
    int mid = (lb+ub)/2;
    int res = getSum(mid);
    res = max(res, getBiggestSize(lb,mid-1,dep-1));
    res = max(res, getBiggestSize(mid+1,ub,dep-1));
    return res;
}

int getIndex(int i) {
    int lb=0, ub=n-1;
    while(lb < ub) {
        int mid=(lb+ub)/2;
        int sm = getSum(mid);
        int len = 0;
        if(sm != big) {
            while(sm != big) sm = getSum(++mid);
            sm = getSum(--mid);
            while(sm != big) sm = getSum(--mid), len++;
            int res = mid == -1 ? 0 : Ask(mid)[0];
            if(i >= res && i < res+len)
                return mid + 1 + i - res;
            if(res > i) ub = mid-1;
            else lb = mid+len+1;
            continue;
        }
        int res = Ask(mid)[0];
        if(res > i) ub = mid-1;
        else lb = mid+1;
    }
    return lb;
}

int find_best(int N) {
    n = N;
    if(n <= 5000) {
        RE(i,n) {
            int res = getSum(i);
            if(res == 0)
                return i;
        }
    }


    big = getBiggestSize(0,n-1);

    RE(i,big) {
        int j = getIndex(i);
        if(getSum(j) == 0)
            return j;
    }

    return -1;
}

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