Submission #258272

#	Time	Username	Problem	Language	Result	Execution time	Memory
258272		eohomegrownapps	Cave (IOI13_cave)	C++14	0 / 100	361 ms	760 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
/*
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
*/

int n;

int combination[5000];

vector<int> switchstates;
vector<bool> posswitch;
vector<int> doorforswitch;

void exploreCave(int N) {
    /* ... */
	n=N;
	switchstates.resize(n,-1);
	posswitch.resize(n);
	doorforswitch.resize(n);
	for (int i = 0; i<n; i++){
		//cout<<"door "<<i<<'\n';
		//door 0
		//check baseline
		for (int j = 0; j<n; j++){
			if (switchstates[j]==-1){
				combination[j]=0;
			} else {
				combination[j]=switchstates[j];
			}
		}
		for (int ix = 0; ix<n; ix++){
			//cout<<switchstates[ix]<<' ';
		}//cout<<'\n';
		int door = tryCombination(combination);
		int posfordoor = 1;
		if (door==-1||door>i){
			posfordoor = 0;
		}
		//cout<<posfordoor<<'\n';
		int switchind = 0;
		for (int v = 0; (1<<v)<=n; v++){
			//cout<<"bit "<<v<<'\n';
			//try bit i
			int ptr = 0;
			for (int j = 0; j<n; j++){
				if (switchstates[j]==-1){
					combination[j]=bool((1<<v)&ptr);
					ptr++;
				}
			}
			for (int ix = 0; ix<n; ix++){
				//cout<<combination[ix]<<' ';
			}//cout<<'\n';
			int newdoor = tryCombination(combination);
			if (newdoor!=door){
				switchind+=(1<<v);
			}
		}
		//cout<<switchind<<'\n';
		int ptr = 0;
		for (int j = 0; j<n; j++){
			if (switchstates[j]==-1){
				if (ptr==switchind){
					doorforswitch[j]=i;
					posswitch[j]=posfordoor;
					switchstates[j]=posfordoor;
					break;
				}
				ptr++;
			}
		}
	}
	int s[5000],d[5000];
	for (int i = 0; i<n; i++){
		s[i]=posswitch[i];
		d[i]=doorforswitch[i];
	}
	answer(s,d);
}

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