Submission #581693

#	Time	Username	Problem	Language	Result	Execution time	Memory
581693		tranxuanbach	Cave (IOI13_cave)	C++17	51 / 100	632 ms	62412 KiB

cave

#ifndef FEXT

#include "cave.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

#ifdef FEXT

void answer(int S[], int D[]);

int tryCombination(int S[]);

#endif

const int N = 5e3 + 5;

int n;

int s[N], d[N];
int t[N];

int realtryCombination(int S[]){
    int ans = tryCombination(S);
    if (ans == -1){
        ans = n;
    }
    return ans;
}

void find_pos(int pos){
    if (pos == n){
        return;
    }

    vi a;
    For(i, 0, n){
        if (d[i] == -1){
            a.emplace_back(i);
            t[i] = 0;
        }
    }

    int val = (realtryCombination(t) > pos ? 0 : 1);

    int lo = 0, hi = isz(a) - 1;
    while (lo < hi){
        int mid = (lo + hi) >> 1;

        For(i, 0, isz(a)){
            if (i <= mid){
                t[a[i]] = 1;
            }
            else{
                t[a[i]] = 0;
            }
        }

        int tval = (realtryCombination(t) > pos ? 0 : 1);
        if (val != tval){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }

    d[a[lo]] = pos;
    s[a[lo]] = val;
    t[a[lo]] = val;

    find_pos(pos + 1);
}

void exploreCave(int _n){
    n = _n;
    For(i, 0, n){
        d[i] = -1;
    }

    find_pos(0);
    answer(s, d);
}

#ifdef FEXT

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

    FILE *f = fopen("KEK.inp", "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;
}

signed main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int N;
    N = init();
    exploreCave(N);
    printf("INCORRECT\nYour solution did not call answer().\n");
    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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