| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 435684 | Odavey | Cave (IOI13_cave) | C++14 | 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.
//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 5001
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
//int p[MX_N];
//int o[MX_N];
int tryCombination(int S[]);
//int tryCombination(vector<int> S){
// int n = S.size();
// cout << "Trying this combination\n";
// for(int i=0;i<n;++i){
// cout << S[i] << ' ';
// }
// cout << endl;
// bool door[n];
// for(int i=0;i<n;++i){
// door[p[i]] = (S[i] == o[p[i]]);
// }
// for(int i=0;i<n;++i){
// if(!door[i]){
// cout << "It reaches all the way up to door " << i << "!\n";
// return i;
// }
// }
// cout << "It reaches all the way through!\n";
// return -1;
//}
void answer (int S[], int D[]);
//void answer (vector<int> S, vector<int> D){
// int n = S.size();
// for(int i=0;i<n;++i){
// cout << S[i] << " & " << D[i] << endl;
// }
// for(int i=0;i<n;++i){
// if(!(S[i] == o[D[i]] && D[i] == p[i])){
// cout << "WA\n";
// return;
// }
// }
// cout << "AC\n";
// return;
//}
void exploreCave(int N){
map<int, int> k;//lever i -> door j
set<int> dk;//lever i
int pos[N];//correct orientation of lever i
memset(pos, -1, sizeof(pos));
for(int i=0;i<N;++i){
dk.insert(i);
}
for(int root=0;root<N;++root){
int S[N];
//vector<int> S(N);
for(int x : dk){
S[x] = 1;
}
for(auto it=k.begin();it!=k.end();++it){
S[it->first] = pos[it->first];
}
int res = tryCombination(S);
bool O = (res > root || res == -1);
int lo=0, hi=(int)dk.size()-1;
while(lo < hi){
int mid = (lo+hi) >> 1;
int cnt = 0;
for(int x : dk){
if(cnt <= mid){
S[x] = O;
}else{
S[x] = !O;
}
++cnt;
}
res = tryCombination(S);
if(res > root || res == -1){
hi = mid;
}else{
lo = mid+1;
}
}
int cnt = 0;
for(int x : dk){
if(cnt == lo){
k[x] = root;
pos[x] = O;
dk.erase(x);
// cout << "Filled in the door at " << root << ", the switch is " << x << " and the orientation is " << O << endl;
break;
}
++cnt;
}
}
// vector<int> S(N), D(N);
int S[N];
int D[N];
for(int i=0;i<N;++i){
S[i] = pos[i];
D[i] = k[i];
}
answer(S, D);
return;
}