Submission #65080

#	Time	Username	Problem	Language	Result	Execution time	Memory
65080		nvmdava	Cave (IOI13_cave)	C++17	100 / 100	1502 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.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 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 ans[5001], door[5001], send[5001], n;

void find(int l, int r, int id, int in){
	if(l == r){
		ans[l] = in;
		door[l] = id;
		return;
	}
	int m = (l + r) >> 1;
	memset(send, -1, sizeof(send));
	for(int i = l; i <= m; i++){
		send[i] = 1;
	}
	for(int i = 0; i < n; i++){
		if(ans[i] != -1){
			send[i] = ans[i];
		} else if(send[i] == -1){
			send[i] = 0;
		}
	}
	int k = tryCombination(send);
	if(k == -1 || k > id){
		k = 1;
	} else {
		k = 0;
	}
	
	if((in ^ k ) == 0){
		find(l, m, id, k);
	} else {
		find(m + 1, r, id, k ^ 1);
	}
}

void exploreCave(int N) {
	n = N;
	memset(ans, -1, sizeof(ans));
	memset(door, -1, sizeof(door));
	int k;
	for(int j = 0; j < n; j++){
		
		memset(send, -1, sizeof(send));
		for(int i = 0; i < n; i++){
			send[i] = max(send[i], ans[i]);
		}
		for(int i = 0; i < n; i++){
			if(send[i] == -1){
				send[i] = 1;
			}
		}
		k = tryCombination(send);
		if(k == -1 || k > j){
			k = 1;
		} else {
			k = 0;
		}
		find(0, n - 1, j, k);
	}
	
	answer(ans, door);
}
/*


int main() {
    int i, res;

	cin>>N;

    for (i = 0; i < N; ++i) {
        cin>>realS[i];
    }
    for (i = 0; i < N; ++i) {
        cin>>realD[i];
        inv[realD[i]] = i;
    }

    num_calls = 0;
    exploreCave(N);
}*/

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