| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1310764 | nataliaa | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
//#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int v[N]={};
int a[N] ={};
int vis[N]={};
for(int i = 0; i < N; i++) vis[i] = -1;
for(int i = 0; i < N; i++) {
for(int j =0; j < N; j++) {
if(vis[j]!=-1) a[vis[j]] = (a[vis[j]]+1)%2;
}
int ind = 0;
int k = tryCombination(a);
for(int j =0; j < N; j++) {
if(vis[j]!=-1) a[vis[j]] = (a[vis[j]]+1)%2;
}
if(k>i||k==-1) ind = 1;
int l = 0, r= N-1;
while(l<=r) {
int m = (l+r)/2;
for(int j =l; j <= m; j++) {
if(vis[j]!=-1) a[vis[j]] = (a[vis[j]]+1)%2;
}
k = tryCombination(a);
for(int j =l; j <= m; j++) {
if(vis[j]!=-1) a[vis[j]] = (a[vis[j]]+1)%2;
}
if(k >= i||k==-1) r = m-1;
else l=m+1;
}
vis[i] = l;
a[l] = ind;
v[l] =i;
}
answer( a,v);
}
