| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 159606 | maximath_1 | Cave (IOI13_cave) | C++11 | 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 "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define all l, r
int s[5069], d[5069];
bool vis[5069];
/*grader start
vector<int>S, D;
int tryCombination(int ss[], int n){
int minimum=10069;
for(int i=0; i<n; i++){
if(ss[i]!=S[i]){
//door is closed
minimum=min(minimum, D[i]);
}
}
if(minimum==10069) return -1;
return minimum;
}
void answer(int ss[], int dd[], int n){
bool incorrect=false;
for(int i=0; i<n; i++){
if(ss[i]!=S[i]){
incorrect=false; break;
}
}
if(incorrect){
cout<<"WA\n"; exit(0);
}
for(int i=0; i<n; i++){
if(dd[i]!=D[i]){
incorrect=false; break;
}
}
if(incorrect){
cout<<"WA\n"; exit(0);
}
cout<<"AC\n"; exit(0);
}
grader end*/
void flipLever(int l, int r){
for(int i=l; i<=r; i++)
if(!vis[i]) s[i]=1-s[i];
//determined levers are stayed untouched
}
int findLever(int door, int n){
int l=0, r=n-1;
if(tryCombination(s, n)!=door) flipLever(all);
while(l<r){
int md=(l+r)/2;
flipLever(l, md);
int tmp=tryCombination(s, n);
flipLever(l, md);
if(tmp!=door) r=md;
else l=md+1;
}
return l;
}
void exploreCave(int n){
memset(s, 0, sizeof(s));
memset(vis, false, sizeof(vis));
for(int i=0; i<n; i++){
int lv=findLever(i, n);
s[lv]=1-s[lv];
d[lv]=i; vis[lv]=true;
}
answer(s, d, n);
}
/*grader start
int main(){
int n;
S.resize(n); D.resize(n);
cin>>n;
for(int i=0; i<n; i++) cin>>S[i];
for(int i=0; i<n; i++) cin>>D[i];
exploreCave(n);
}
grader end*/