| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1357537 | Charizard2021 | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n){
vector<int> correspondence(1 + n, -1);
vector<int> switchNeed(1 + n, -1);
for(int i = 0; i < n; i++){
int s[n];
for(int j = 0; j < n; j++){
s[j] = 0;
}
for(int j = 0; j < i; j++){
s[correspondence[j]] = switchNeed[j];
}
if(tryCombination(s) == i){
switchNeed[i] = 1;
}
else{
switchNeed[i] = 0;
}
int low = 0;
int high = n - 1;
int res = -1;
while(low < high){
int mid = (low + high)/2;
int s2[n];
for(int j = 0; j < n; j++){
s2[j] = 1 - switchNeed[i];
}
for(int j = low; j <= mid; j++){
s2[j] = switchNeed[i];
}
for(int j = 0; j < i; j++){
s2[correspondence[j]] = switchNeed[j];
}
if(tryCombination(s2) == i){
low = mid + 1;
}
else{
high = mid;
}
}
correspondence[i] = low;
}
answer(finalS, d);
}