Submission #107221

#	Time	Username	Problem	Language	Result	Execution time	Memory
107221		SecretAgent007	Cave (IOI13_cave)	C++17	100 / 100	454 ms	612 KiB

cave

#include <bits/stdc++.h>
using namespace std;
#include "cave.h"

const int INF = INT_MAX;
///////////////////////////////////////////////////


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);
}
*/

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24