Submission #1313401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313401		shirokito	동굴 (IOI13_cave)	C++20	100 / 100	196 ms	528 KiB

cave

#ifndef LOCAL
    #include "cave.h"
#endif

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

#define all(a) (a).begin(), (a).end()
#define fi first
#define se second

using ll = long long;

const int N = 5000 + 24;
const int MAX_CALL = 70000;

mt19937_64 rng(36363636);

#ifdef LOCAL
int n, real_s[N], real_d[N];
int cnt_query;

int tryCombination(int S[]) {

    cnt_query++;
    if (cnt_query > MAX_CALL) {
        cout << "CALL TOO MUCH" << endl;
        exit(0);
    }

    for (int i = 0; i < n; i++) {
        // cout << S[i] << ' ';
    }
    // cout << endl;

    vector<int> state(n);

    for (int i = 0; i < n; i++) {
        int j = real_d[i];
        state[j] = (S[i] == real_s[i]);

    }
        
    // cout << "STATE: ";
    // for (int j = 0; j < n; j++) cout << state[j] << ' '; cout << endl;

    for (int i = 0; i < n; i++) {
        if (!state[i]) return i;
        // if (!state[i]) return cout << i << endl, i;
    }

    return -1;

    // return cout << -1 << endl, -1;
}

void answer(int S[], int D[]) {
    bool valid = 1;

    for (int i = 0; i < n; i++) {
        if (S[i] != real_s[i]) {
            valid = 0;
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        if (D[i] != real_d[i]) {
            valid = 0;
            break;
        }
    }

    if (!valid) {
        cout << "WRONG ANSWER" << endl;
        cout << "EXPECTED OUTPUT" << endl;

        for (int i = 0; i < n; i++) cout << real_s[i] << ' '; cout << endl; 
        for (int i = 0; i < n; i++) cout << real_d[i] << ' '; cout << endl; 
        
        cout << "YOUR OUTPUT" << endl;

        for (int i = 0; i < n; i++) cout << S[i] << ' '; cout << endl; 
        for (int i = 0; i < n; i++) cout << D[i] << ' '; cout << endl; 
    }
    else {
        cout << "CORRECT" << endl;
    }
}

#endif

void exploreCave(int N) {
    int n = N;

    int state[n], new_state[n];
    int can[n], d[n];

    for (int i = 0; i < n; i++) {
        d[i] = -1;
    }

    for (int i = 0; i < n; i++) {
        state[i] = new_state[i] = 0;
        can[i] = 1;
    }

    for (int i = 0; i < n; i++) {
        int k = tryCombination(state);
        
        if (k == -1) break;

        int m = tryCombination(can);

        if (m != -1 && m < k) {
            int pos = -1;

            for (int l = 1, r = n - i; l <= r; ) {
                int mid = (l + r) >> 1, p;

                for (int i = 0; i < n; i++) {
                    new_state[i] = state[i];
                }

                for (int i = 0, j = 0; i < n; i++) {
                    if (can[i]) {
                        new_state[i] = 1;
                        if (!state[i]) j++;
                    }
                    if (j == mid) {
                        p = i;
                        break;
                    }
                }

                // cout << mid << '.' << p << endl;

                int jury_ans = tryCombination(new_state);

                if (jury_ans == m) {
                    pos = p;
                    r = mid - 1;
                }
                else l = mid + 1;
            }

            if (pos != -1) {
                can[pos] = 0;
                d[pos] = m;
                // cout << "POS = " << pos << "\n";
            }
        }

        else {
            int pos = -1;
        
            for (int l = 1, r = n - i; l <= r; ) {
                int mid = (l + r) >> 1, p;

                for (int i = 0; i < n; i++) {
                    new_state[i] = state[i];
                }

                for (int i = 0, j = 0; i < n; i++) {
                    if (can[i]) {
                        new_state[i] = 1;
                        if (!state[i]) j++;
                    }
                    if (j == mid) {
                        p = i;
                        break;
                    }
                }

                // cout << mid << '.' << p << endl;

                int jury_ans = tryCombination(new_state);

                if (jury_ans == -1 || jury_ans > k) {
                    pos = p;
                    r = mid - 1;
                }
                else l = mid + 1;  
            }

            if (pos != -1) {
                // cout << "POS = " << pos << "\n";
                state[pos] = 1;
                d[pos] = k;
            }
        }

        // cout << cnt_query << endl;
    }


    for (int i = 0; i < n; i++) {
        if (d[i] != -1) continue;
        for (int j = 0; j < n; j++) {
            new_state[j] = state[j];
        }
        new_state[i] ^= 1;
        d[i] = tryCombination(new_state);
    }

    return answer(state, d);
}

#ifdef LOCAL 
void solve() {
    // cin >> n; 
    n = 5000;

    cnt_query = 0;

    for (int i = 0; i < n; i++) {
        // cin >> real_s[i];
        real_s[i] = rng() % 2;
    }

    for (int i = 0; i < n; i++) {
        // cin >> real_d[i];
        real_d[i] = i;
    }

    shuffle(real_d, real_d + n, rng);

    exploreCave(n);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 100; // cin >> T;
    while (T--) {
        solve();
    }
}
#endif

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