Submission #870628

#	Time	Username	Problem	Language	Result	Execution time	Memory
870628		Irate	Cave (IOI13_cave)	C++14	100 / 100	249 ms	756 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
// #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 n;
// int tryCombination(int S[]) {
//     int i;

//     if (num_calls >= MAX_CALLS) {
//         printf("INCORRECT\nToo many calls to tryCombination().\n");
//         exit(0);
//     }
//     for(int i = 0;i < n;++i){
//     	cout << S[i] << ' ';
//     }
//     cout << '\n';
//     ++num_calls;

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

// int init() {
//     int i, res;

//     FILE *f = fopen("cave.in", "r");
// 	if (!f)
// 		fail("Failed to open input file.");

// 	res = fscanf(f, "%d", &N);

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

//     num_calls = 0;
//     return N;
// }

void exploreCave(int n){
	int v[n];
	int res[n];
	for(int i = 0;i < n;++i){
		v[i] = 0;
		res[i] = -1;
	}	
	for(int i = 0;i < n;++i){
		if(tryCombination(v) != i){
			for(int j = 0;j < n;++j){
				if(res[j] == -1)v[j] ^= 1;
			}
		}
		int l = 0, r = n - 1, ans = -1;
		while(l <= r){
			int mid = (l + r) >> 1;
			for(int j = l;j <= mid;++j){
				if(res[j] == -1)v[j] ^= 1;
			}
			int check = tryCombination(v);
			for(int j = l;j <= mid;++j){
				if(res[j] == -1)v[j] ^= 1;
			}
			if(check > i || check == -1){
				r = mid - 1;
				ans = mid;
			}
			else{
				l = mid + 1;
			}
		}
		res[ans] = i;
		v[ans] ^= 1;
	}
	answer(v, res);
}

// int main()
// {
// 	cin >> n;
// 	for(int i = 0;i < n;++i){
// 		cin >> realS[i];
// 	}
// 	for(int i = 0;i < n;++i){
// 		cin >> realD[i];
// 	}
// 	exploreCave(n);
// }

Compilation message (stderr)

cave.cpp:7:1: warning: multi-line comment [-Wcomment]
    7 | // #define fail(s, x...) do { \
      | ^

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