| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 442386 | DmitryGrigorev | Counting Mushrooms (IOI20_mushrooms) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 1000000007;
void add(int& a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int mult(int a, int b) {
return a * (ll)b % mod;
}
int bp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int WANT = 150000;
int N = 10;
int ITER = 100;
int count_mushrooms(int n) {
srand(time(0));
vector<int> a, b, undef;
a.pb(0);
for (int i = 1; i < n; ++i) undef.pb(i);
vector<int> v;
for (int i = 0; i < N; ++i) v.pb(i);
random_shuffle(all(undef));
while (a.size() < WANT && b.size() < WANT && undef.size()) {
if (undef.size() < N) {
int lt = undef.back();
undef.pop_back();
vector<int> req = {a[0], lt};
int res = use_machine(req);
if (res == 0) a.pb(lt);
else b.pb(lt);
}
else {
vector<int> guys;
for (int i = 0; i < N; ++i) {
guys.pb(undef.back());
undef.pop_back();
}
vector<int> W;
for (int j = 0; j < (1<<N); ++j) W.pb(j);
while (W.size() != 1) {
int bans = W.size();
vector<int> best_x;
int our_cost;
for (int a = 0; a < ITER; ++a) {
random_shuffle(all(v));
auto perm = v;
vector<int> cnt(20, 0);
int T = 0;
for (auto i : W) {
vector<int> arr;
int last = -1;
int S = 0;
for (int j = 0; j < N; ++j) {
int nn;
if (perm[j] == N-1) nn = 0;
else if ((1<<perm[j])&i) nn=1;
else nn=0;
if (nn!=last && last!=-1) S++;
last = nn;
}
cnt[S]++;
T = max(T, cnt[S]);
}
if (T < bans) {
bans = T;
best_x = perm;
}
}
vector<int> req;
for (auto el : best_x) {
if (el == N-1) req.pb(a[0]);
else req.pb(guys[el]);
}
our_cost = use_machine(req);
vector<int> tt;
for (auto i : W) {
vector<int> arr;
for (int j = 0; j < n; ++j) {
if (best_x[j] == n-1) arr.pb(0);
else if ((1<<best_x[j])&i) arr.pb(1);
else arr.pb(0);
}
int S = 0;
for (int j = 1; j < arr.size(); ++j) if (arr[j] != arr[j-1]) S++;
if (S == our_cost) tt.pb(i);
}
W=tt;
}
int mask = W[0];
for (int j = 0; j < mask; ++j) {
if ((1<<j)&mask) b.pb(guys[j]);
else a.pb(guys[j]);
}
}
}
}
#ifdef LOCAL
int main(){
freopen("C_input.txt", "r", stdin);
//freopen("C_output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
}
#endif