| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 759078 | Fidisk | Cave (IOI13_cave) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;
vector<pii> correctPart,stablePart,questionPart,inversePart;
vector<int> ans1,ans2,queryVect;
/*
int tryCombination(vector<int> ans) {
for (int i=0;i<ans.size();i++) {
cout<<ans[i]<<' ';
}
cout<<'\n';
//cout<<"Query completed!\n";
int kq;
cin>>kq;
return kq;
}
void answer(vector<int> x,vector<int> y) {
for (int i=0;i<x.size();i++) {
cout<<x[i]<<' ';
}
cout<<'\n';
for (int i=0;i<y.size();i++) {
cout<<y[i]<<' ';
}
cout<<'\n';
}
*/
int query() {
//cout<<"We're here 2\n";
//return 0;
int k=correctPart.size();
for (int i=0;i<k;i++) {
queryVect[correctPart[i].fi]=correctPart[i].se;
}
k=stablePart.size();
for (int i=0;i<k;i++) {
queryVect[stablePart[i].fi]=stablePart[i].se;
}
k=questionPart.size();
for (int i=0;i<k;i++) {
queryVect[questionPart[i].fi]=questionPart[i].se;
}
k=inversePart.size();
for (int i=0;i<k;i++) {
queryVect[inversePart[i].fi]=inversePart[i].se^1;
}
k=tryCombination(queryVect);
//cout<<k<<'\n';
if (k<0) {
return 5001;
}
return k;
}
void exploreCave(int n) {
int m=n;
correctPart.clear();
stablePart.clear();
questionPart.clear();
inversePart.clear();
queryVect.resize(n);
for (int i=0;i<n;i++) {
questionPart.push_back({i,0});
}
while (m>0) {
int p=n-m;
int k=questionPart.size();
//cout<<"We're here\n";
//return;
//cout<<p<<"Reset\n";
if (query()==p) {
//cout<<"Flip!\n";
for (int i=0;i<k;i++) {
questionPart[i].se^=1;
}
}
//for (int i=0;i<k;i++) {
// cout<<questionPart[i].fi<<"|"<<questionPart[i].se<<' ';
//}
//cout<<'\n';
while (k>1) {
for (int i=0;i<k/2;i++) {
inversePart.push_back(questionPart.back());
questionPart.pop_back();
}
if (query()==p) {
k=questionPart.size();
for (int i=0;i<k;i++) {
stablePart.push_back(questionPart.back());
questionPart.pop_back();
}
swap(questionPart,inversePart);
}
else {
k=inversePart.size();
for (int i=0;i<k;i++) {
stablePart.push_back(inversePart.back());
inversePart.pop_back();
}
}
k=questionPart.size();
}
correctPart.push_back(questionPart.back());
//cout<<correctPart.back().fi<<' '<<correctPart.back().se<<'\n';
questionPart.clear();
swap(questionPart,stablePart);
m--;
}
ans1.resize(n);
ans2.resize(n);
for (int i=0;i<n;i++) {
ans2[correctPart[i].fi]=i;
}
for (int i=0;i<n;i++) {
ans1[correctPart[i].fi]=correctPart[i].se;
}
answer(ans1,ans2);
}