제출 #821107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821107		vjudge1	The Big Prize (IOI17_prize)	C++17	20 / 100	3049 ms	324 KiB

prize

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

using namespace std;

// ask

struct MY{
    set < pair < int, int > > L, R;

    MY() {
        L.insert({0, 0});
        R.insert({200200, 0});
    }

    void add_l(int pos, int val) {
        L.insert({pos, val});
    }

    void add_r(int pos, int val) {
        R.insert({pos, val});
    }

    int find_l(int m) {
        return prev(L.upper_bound({m, 200200}))->second; 
    }
    
    int find_r(int m) {
        return R.upper_bound({m - 1, 200200})->second;
    }
};

map < int, pair < int, int > > mp;
map < int, MY > cnt;

pair < int, int >  check(int i) {
    auto it = mp.find(i);
    if(it != mp.end()) {
        return it->second;
    }
    mp[i];
    it = mp.find(i);
    auto res = ask(i - 1);
    it->second = {res[0], res[1]};
    return it->second;
}

int recur(int l, int r) {
    int m = (l + r) / 2;
    auto [a, b] = check(m);
    if(a + b < 2) {
        return m;
    }
    int c = a + b;
    auto it = cnt.find(c);
    if(it == cnt.end()) {
        cnt[c];
        it = cnt.find(c);
    }
    it->second.add_l(m, a);
    it->second.add_r(m, b);
    a -= it->second.find_l(l);
    b -= it->second.find_r(r);
    if(a > b) {
        return recur(l, m);
    }
    return recur(m, r);
}

int find_best(int n) {
	int l = 0, r = n + 1, m;
    mp[l] = {0, 0};
    mp[r] = {0, 0};
    for(;;) {
        m = recur(l, r);    
        auto [a, b] = check(m);
        if(a|b) {
            (a ? r : l) = m;
        } else {
            break;
        }
    }
    return m - 1;
}

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