Submission #300008

#	Time	Username	Problem	Language	Result	Execution time	Memory
300008		MarcoMeijer	커다란 상품 (IOI17_prize)	C++14	20 / 100	3049 ms	1452 KiB

prize

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

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=1e5;

map<int, vi> mem;
map<int, map<int, int>> bst;

vi Ask(int i) {
    if(mem.count(i)) return mem[i];
    vi ret = ask(i);
    return mem[i] = ret;
}

int find_best(int n) {
    int sq = ceil(sqrt(n))+1;
    int mn = min(sq*2+1, n);

    int sm = 0;
    RE(i,mn) {
        vi res = Ask(i);
        sm = max(sm, res[0]+res[1]);
    }

    vi g;
    RE(i,sm) {
        int lb=0, ub=n-1;
        if(g.size()) lb=g.back()+1;
        while(lb != ub) {
            int mid=(lb+ub+1)/2;
            vi res = Ask(mid);
            if(res[0] + res[1] == sm) {
                if(res[0] > i) ub=mid-1;
                else lb=mid+1;
                if(lb == ub) g.pb(lb);
            } else {
                int j = mid;
                while(1) {
                    j--;
                    if(j == -1) {
                        lb = ub = 0;
                        break;
                    }
                    res = Ask(j);
                    if(res[0] + res[1] == sm) {
                        if(res[0] == i) {
                            lb = ub = j+1;
                        }
                        break;
                    }
                }
                if(lb == ub) {
                    REP(k,lb,mid+1) {
                        g.pb(k);
                    }
                    i += mid-lb;
                } else {
                    res = Ask(j);    
                    if(res[0] > i) ub=j-1;
                    else lb=j+1;
                    if(lb == ub) g.pb(lb);
                }
            }
        }
    }
    RE(i,sm) {
        vi res = Ask(g[i]);
        if(res[0]+res[1] == 0) return g[i];
    }
    return 0;
}

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