Submission #1264443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264443		aren_dance	커다란 상품 (IOI17_prize)	C++20	0 / 100	3 ms	1548 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int>> mp;
vector<int> per(int x) {
    if (x == -1) {
        return {};
    }
    if (mp.find(x) == mp.end()) {
        vector<int> u = ask(x);
        mp[x] = u;
    }
    return mp[x];
}
int find_best(int n) {
  vector<int> p;
for (int i = 0;i < n;++i) {
    p.push_back(i);
}
while (true) {
    int x = p.size();
    int e = 0;
    for (int i = 0;i * i < x;++i) {
        vector<int> f = per(p[i]);
        e = max(e,f[0]+f[1]);
        if (e == 0) {
            return i;
        }
    }
    set<pair<int, int>> st;
    st.insert({ 0, x-1});
    for (int i = 0;i < 20;++i) {
        vector<int> v;
        set<pair<int, int>> st1;
        for (auto j = st.begin();j != st.end();++j) {
            int x = (*j).first;
            int y = (*j).second;
            if (x == y) {
                v.push_back(i);
                continue;
            }
            int m = (x + y) / 2;
            vector<int> f1 = per(x);
            vector<int> f2 = per(m);
            vector<int> f3 = per(y);
            int sum1 = f1[0] + f1[1];
            int sum2 = f2[0] + f2[1];
            int sum3 = f3[0] + f3[1];
            if (sum1 == 0) {
                return x;
            }
            if (sum2 == 0) {
                return m;
            }
            if (sum3 == 0) {
                return y;
            }
            if (f2[0] != f1[0]) {
                st1.insert({x,m});
            }
            if (f2[1]+f2[0] == e && (f1[1]!=f2[1])) {
                st1.insert({m+1,y});
            }
            if (f2[1] + f2[0] != e) {
                vector<int> f4 = per(m+1);
                if (f4[0] == 0 && f4[1] == 0) {
                    return m+1;
                }
                if (f4[1]!=f3[1]) {
                    st1.insert({m+1,y});
                }
            }
        }
        p = v;
        st1 = st;
    }
}
}

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