| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1264442 | aren_dance | 커다란 상품 (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#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;
}
}
}
}