| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 107219 | SecretAgent007 | 동굴 (IOI13_cave) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "cave.h"
#define int long long
const int INF = 1e18;
///////////////////////////////////////////////////
vector< int > input;
vector< int > openWith;
int n;
vector< int > known;
void flip(int a, int b, int v[]){
for(int i = a; i <= b; i++){
if(known[i] != -1) v[i] = known[i];
else if(v[i] == 0) v[i] = 1;
else v[i] = 0;
}
}
int interrupt;
bool type;
void query(int l, int r, int door, bool greater, int v[]){
if(l == r){
interrupt = l;
if(greater){
type = v[l];
}else{
if(v[l]) type = 0;
else type = 1;
}
return;
}
int mid = (l+r)/2;
if(greater){
flip(l,mid,v);
int re = tryCombination(v);
if(re == -1) re = INF;
if(re > door){
query(mid+1,r,door,1,v);
}else{
query(l,mid,door,0,v);
}
}else{
flip(l,mid,v);
int re = tryCombination(v);
if(re == -1) re = INF;
if(re > door){
query(l,mid,door,1,v);
}else{
query(mid+1,r,door,0,v);
}
}
}
void exploreCave(int N){
known.assign(N,-1);
int v[N];
int D[N];
bool verif;
int S[N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++) v[j] = 1;
flip(0,N-1,v);
int r = tryCombination(v);
if(r == -1 || r > i) verif = true;
else verif = false;
query(0,N-1,i,verif,v);
D[interrupt] = i;
known[interrupt] = type;
S[interrupt] = type;
}
answer(S,D);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
input.resize(n);
openWith.resize(n);
for(int i = 0; i < n; i++){
cin >> input[i];
}
for(int i = 0; i < n; i++){
cin >> openWith[i];
}
exploreCave(n);
}