Submission #1313358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313358		lmaobruh	커다란 상품 (IOI17_prize)	C++20	100 / 100	20 ms	948 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ll long long
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define ve vector
#define all(x) x.begin(), x.end()
#define fo(i,a,b) for (int i=(a); i<=(b); ++i)
#define fd(i,a,b) for (int i=(a); i>=(b); --i)
#define popcount(x) __builtin_popcountll(x)
#define maxi(a, b) a = max(a, b)
#define mini(a, b) a = min(a, b)
#define siz(x) ((int)(x).size())
#define vi ve<int>
#define _ << ' ' <<

const int N = 1e6+5, inf = 1e9+10, mod = 1e9+7, sq = 447;

map<int, vi> mem;
bool finish = 0;

vi get(int x) {
    if (!mem.count(x)) {
        mem[x] = ask(x);
        if (mem[x] == vi{0, 0}) finish = 1;
    }
    return mem[x];
}

int tot, len;

void rec(int l, int r) {
    if (l > r || finish) return;
    if (l == r) {
        get(l);
        return;
    }

    int m1 = (l + r) >> 1, m2 = m1;
    get(m1);

    while (m1 > l && get(m1)[0] + get(m1)[1] < tot) m1--;

    if (l < m1 && ((l == 0 && get(m1)[0]) || (l && get(m1)[0] > get(l-1)[0]))) {
        rec(l, m1-1);
    }

    while (m2 < r && get(m2)[0] + get(m2)[1] < tot) m2++;

    if (m2 < r && ((r == len - 1 && get(m2)[1]) || (r + 1 < len && get(m2)[1] > get(r+1)[1]))) {
        rec(m2+1, r);
    }
}

mt19937_64 rng((ll)(new char));

int find_best(int n) {
    len = n;
    int pos = 0, best = 0;
    fo(i,1,min(n,240)) {
        int P = rng()%n;
        vi ans = get(P);
        if (ans[0] + ans[1] > best) {
            best = ans[0] + ans[1];
            pos = P;
        }
    }
    tot = best;

    rec(0, n-1);

    fo(i,0,n-1) {
        if (mem.count(i) && mem[i][0] + mem[i][1] == 0) {
            return i;
        }
    }

    assert(0);
}

//void sol() {
//
//}
//
//signed main(){
//    ios::sync_with_stdio(0); cin.tie(0);
//    if(fopen("A.inp","r")) {
//        freopen("A.inp","r",stdin);
//        freopen("A.out","w",stdout);
//    }
//    int tc = 1; // cin >> tc;
//    fo(i,1,tc) sol();
//    return 0;
//}

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