Submission #687366

#	Time	Username	Problem	Language	Result	Execution time	Memory
687366		Bliznetc	Cave (IOI13_cave)	C++17	100 / 100	300 ms	472 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second

#define MAX_N 5000
#define MAX_CALLS 70000

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

/*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;
 
//    for (i = 0; i < N; i++) {
//        cout << S[i] << " ";
//    }
//    cout << "\n";
    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("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 ask[n];
    int good[n];
    int d[n];
    for (int i = 0; i < n; i++) {
        good[i] = d[i] = -1;
    }
//    vector<int> good(n, -1), d(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (good[j] == -1) {
                ask[j] = 0;
            }
            else {
                ask[j] = good[j];
            }
        }

        int x = tryCombination(ask);
        if (x == i) {
            for (int j = 0; j < n; j++) {
                if (good[j] == -1) {
                    ask[j] = 1;
                }
                else {
                    ask[j] = good[j];
                }
            }
        }

        int l = 0, r = n - 1;
        while (r - l > 0) {
            int mid = (l + r) / 2;
            for (int j = l; j <= mid; j++) {
                if (good[j] == -1) {
                    ask[j] = 1 - ask[j];
                }
                else {
                    ask[j] = good[j];
                }
            }

            x = tryCombination(ask);
//            cout << i << " - " << x << " " << l << " " << r << "\n";
            if (x == i) {
                for (int j = l; j <= mid; j++) {
                    if (good[j] == -1) {
                        ask[j] = 1 - ask[j];
                    }
                    else {
                        ask[j] = good[j];
                    }
                }
                for (int j = mid + 1; j <= r; j++) {
                    if (good[j] == -1) {
                        ask[j] = 1 - ask[j];
                    }
                    else {
                        ask[j] = good[j];
                    }
                }
                r = mid;
            }
            else {
                l = mid + 1;
            }
//            cout << l << " " << r << ":\n";
//            for (int j = 0; j < n; j++) {
//                cout << ask[j] << " ";
//            }
//            cout << "\n";
        }


        /*if (good[l] == -1) {
            ask[l] = 1 - ask[l];
        }
        else {
            ask[l] = good[l];
        }
        x = tryCombination(ask);
        if (x == i) {
            if (good[l] == -1) {
                ask[l] = 1 - ask[l];
            }
            else {
                ask[l] = good[l];
            }
            l = r;
        }*/

        good[l] = ask[l];
        d[l] = i;
//        cout << i << " - " <<  l << " " << good[i] << " " << d[l] << "\n";
//        cout << "\n";
    }

    answer(good, d);
}

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

/*
signed main() {
    vi a;
    a.pb(-2);
    a.pb(2);
    a.pb(2);
    a.pb(-2);
    a.pb(-2);
    a.pb(2);
    cout << count_swaps(a);
}
 */

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