Submission #569658

#	Time	Username	Problem	Language	Result	Execution time	Memory
569658		joshjms	Cave (IOI13_cave)	C++14	100 / 100	1145 ms	660 KiB

cave

#include "cave.h"

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

#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;

// #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;
// }

int n, a[100000], c[100000], x[100000], v[100000], p[100000];

void exploreCave(int N) {
    n = N;

    for(int i = 0; i < n; i++) {

        for(int j = 0; j < n; j++)
            if(!v[j]) a[j] = 0;

        int X = tryCombination(a);
        if(X == -1) X = n;

        // for(int j = 0; j < n; j++)
        //     cout << a[j] << " ";
        // cout << "\n";

        // debug(X);

        int u = (X > i ? 0 : 1);

        int l = 0, r = n - 1;

        while(l <= r) {
            int mid = (l + r) / 2;

            for(int j = 0; j < n; j++) {
                if(v[j]) continue;
                if(j < l || j > r) a[j] = u ^ 1;
                else if(j <= mid) a[j] = u;
                else a[j] = u ^ 1;
            }

            // for(int j = 0; j < n; j++)
            //     cout << a[j] << " ";
            // cout << "\n";

            int Y = tryCombination(a);
            if(Y == -1) Y = n;

            // debug(Y);

            if(Y > i) r = mid - 1, c[i] = mid;
            else l = mid + 1;
        }

        // debug(c[i]);
        
        a[c[i]] = u;
        v[c[i]] = 1;
    }

    // for(int i = 0; i < n; i++)
    //     cout << c[i] << " ";
    // cout << "\n";

    for(int i = 0; i < n; i++)
        p[c[i]] = i;

    answer(a, p);
}

// int main() {
//     int N;
// 	N = init();
// 	exploreCave(N);
//     printf("INCORRECT\nYour solution did not call answer().\n");
// 	return 0;
// }

Compilation message (stderr)

cave.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | // #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