| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 434800 | rqi | Cat in a tree (BOI17_catinatree) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long double db;
#define pb push_back
#define bk back()
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
mt19937 rng(127);
int count_mushrooms(int n) {
// cout << fixed << setprecision(6);
// cout << db(226*100)/(db(98.0)) << "\n";
vi known[2];
vi untested;
int ans = 1;
known[0].pb(0);
for(int i = 1; i < n; i++){
untested.pb(i);
}
shuffle(all(untested), rng);
const int BLOCK = sqrt(n)/2;
vi p = vi{0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0};
while(sz(untested)){
int better_ind = 0;
if(sz(known[1]) > sz(known[0])) better_ind = 1;
if(sz(known[better_ind]) < 2 || sz(known[better_ind]) > BLOCK){
// cout << "known: " << sz(known[better_ind]) << "\n";
// cout << "untested: " << sz(untested) << "\n";
vi to_test;
int to_go = sz(untested);
int special = untested.bk; untested.pop_back();
to_test.pb(special);
to_test.pb(known[better_ind][0]);
vi tested;
for(int i = 1; i < min(to_go, sz(known[better_ind])); i++){
tested.pb(untested.bk);
to_test.pb(untested.bk); untested.pop_back();
to_test.pb(known[better_ind][i]);
}
bool do_special = 0;
if(sz(untested) > 0){
do_special = 1;
}
int res = use_machine(to_test);
int special_identity = better_ind;
if(res % 2 == 0){
}
else{
special_identity^=1;
}
known[special_identity].pb(special);
if(special_identity == 0){
ans++;
}
// cout << res/2 << " " << sz(tested) << "\n";
if(res/2 == sz(tested)){
for(auto u: tested){
known[better_ind^1].pb(u);
}
}
else if(res/2 == 0){
for(auto u: tested){
known[better_ind].pb(u);
}
}
if(better_ind == 0){
ans+=sz(tested)-res/2;
}
else{
ans+=res/2;
}
}
else{
vi tested;
for(int i = 0; i < 2; i++){
tested.pb(untested.bk); untested.pop_back();
}
vi to_test = vi{tested[0], known[better_ind][0], tested[1], known[better_ind][1]};
int res = use_machine(to_test);
for(int i = 0; i < 2; i++){
int special_ind = better_ind;
if((res>>i)&1){
special_ind = better_ind^1;
}
else{
}
known[special_ind].pb(tested[i]);
}
}
// else{
// cout << "DOING SPECIAL" << "\n";
// vi to_test;
// vi tested;
// cout << "sz(known[better_ind]):" << " " << sz(known[better_ind]) << "\n";
// cout << "sz(untested): " << sz(untested) << "\n";
// int to_go = sz(untested);
// for(int i = 0; i < min(to_go, 2*sz(known[better_ind])); i++){
// tested.pb(untested.bk); untested.pop_back();
// }
// cout << "tested: ";
// for(auto u: tested){
// cout << u << " ";
// }
// cout << "\n";
// for(auto u: tested){
// cout << p[u] << " ";
// }
// cout << "\n";
// to_test.pb(tested[0]);
// to_test.pb(known[better_ind][0]);
// for(int i = 1; i+1 < sz(tested); i+=2){
// to_test.pb(tested[i]);
// to_test.pb(tested[i+1]);
// to_test.pb(known[better_ind][(i+1)/2]);
// }
// if(sz(tested) % 2 == 0){
// to_test.pb(tested.bk);
// }
// cout << "to_test: ";
// for(auto u: to_test){
// cout << u << " ";
// }
// cout << "\n";
// for(auto u: to_test){
// cout << p[u] << " ";
// }
// cout << "\n";
// int res = use_machine(to_test);
// cout << "res: " << res << "\n";
// // cout << sz(known[better_ind]) << "\n";
// // cout << res/2 << " " << sz(tested) << "\n";
// // if(res/2 == sz(tested)){
// // for(auto u: tested){
// // known[better_ind^1].pb(u);
// // }
// // }
// // else if(res/2 == 0){
// // for(auto u: tested){
// // known[better_ind].pb(u);
// // }
// // }
// if(better_ind == 0){
// ans+=sz(tested)-res;
// }
// else{
// ans+=res;
// }
// }
}
return ans;
}