Submission #488112

#	Time	Username	Problem	Language	Result	Execution time	Memory
488112		ssense	Cave (IOI13_cave)	C++14	100 / 100	1793 ms	552 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
/*
#define MAX_N 5000
#define MAX_CALLS 70000

#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

//Symbol obfuscation
#define N koala
#define realS kangaroo
#define realD possum
#define inv platypus
#define num_calls echidna

static int N;
static int realS[MAX_N];
static int realD[MAX_N];
static int inv[MAX_N];
static int num_calls;

void answer(int S[], int D[]) {
	int i;
	int correct = 1;
	for (i = 0; i < N; ++i)
		if (S[i] != realS[i] || D[i] != realD[i]) {
			correct = 0;
			break;
		}

	if (correct)
		printf("CORRECT\n");
	else
		printf("INCORRECT\n");

	for (i = 0; i < N; ++i) {
		if (i > 0)
			printf(" ");
		printf("%d", S[i]);
	}
	printf("\n");

	for (i = 0; i < N; ++i) {
		if (i > 0)
			printf(" ");
		printf("%d", D[i]);
	}
	printf("\n");

	exit(0);
}

int tryCombination(int S[]) {
	int i;

	if (num_calls >= MAX_CALLS) {
		printf("INCORRECT\nToo many calls to tryCombination().\n");
		exit(0);
	}
	++num_calls;

	for (i = 0; i < N; ++i)
		if (S[inv[i]] != realS[inv[i]])
			return i;
	return -1;
}

int init() {
	int i, res;

	res = scanf("%d", &N);

	for (i = 0; i < N; ++i) {
		res = scanf("%d", &realS[i]);
	}
	for (i = 0; i < N; ++i) {
		res = scanf("%d", &realD[i]);
		inv[realD[i]] = i;
	}

	num_calls = 0;
	return N;
}
*/
void exploreCave(int n)
{
	int set[n];
	int lever[n];
	for(int i = 0; i < n; i++)
	{
		set[i] = -1;
		lever[i] = -1;
	}
	for(int door = 0; door < n; door++)
	{
		int q[n];
		for(int i = 0; i < n; i++){
			if(set[i] != -1)
			{
				q[i] = set[i];
			}
			else
			{
				q[i] = 0;
			}
		}
		int now = tryCombination(q);
		if(now != door){
			now = 0;
		}
		else{
			now = 1;
		}
		int modulo = 0;
		for(int md = 2; md < 2*n; md*=2)
		{
			for(int i = 0; i < n; i++)
			{
				if(i%md == modulo)
				{
					q[i] = now;
				}
				else
				{
					q[i] = 1-now;
				}
				if(set[i] != -1)
				{
					q[i] = set[i];
				}
			}
			int query = tryCombination(q);
			if(query == door)
			{
				modulo+=md/2;
			}
		}
		set[modulo] = now;
		lever[modulo] = door;
	}
	answer(set, lever);
}
/*

int32_t main(){
	startt
	int N;
	N = init();
	exploreCave(N);
	printf("INCORRECT\nYour solution did not call answer().\n");
	return 0;
}
 */
/*
4
1 1 1 0
3 1 0 2
 */

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