Submission #670394

#	Time	Username	Problem	Language	Result	Execution time	Memory
670394		illyakr	Cave (IOI13_cave)	C++14	100 / 100	733 ms	720 KiB

cave

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

using namespace std;

void exploreCave(int N) {
    int S[N], D[N];
    int ask[N];
    vector<pair<int, int> > know;
    for (int i = 0; i < N; i++) {
        S[i] = 0;
        D[i] = i;
    }

    for (int id = 0; id < N; id++) {
        for (int i = 0; i < N; i++)ask[i] = 0;
        for (auto [id, val] : know)ask[id] = val;

        int correctVal = 0;

        int cur = tryCombination(ask);
        if (cur == -1 || cur > id)correctVal = 0;
        else correctVal = 1;

//        cout << id << ": ";
//        for (int i = 0; i < N; i++)
//            cout << ask[i] << " ";
//        cout << " =-=-= " << correctVal << endl;
//        cout << "Are you sure???????????" << endl;

        int l = -1, r = N;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            for (int i = 0; i < N; i++)ask[i] = (correctVal ^ 1);
            for (int i = 0; i <= mid; i++)
                ask[i] = correctVal;
            for (auto [id, val] : know)ask[id] = val;

//            cout << "Guess " << l << " " << r << "   " << mid << endl;
//            for (int i = 0; i < N; i++)
//                cout << ask[i] << " ";

            int curInfo = tryCombination(ask);
//            cout << " ======  " << curInfo << endl;
            if (curInfo == -1 || curInfo > id)r = mid;
            else l = mid;
        }
//        cout << "It is " << r << endl << endl;
        S[r] = correctVal;
        D[r] = id;
        know.push_back({r, correctVal});
    }
    answer(S, D);
    /* ... */
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:17:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |         for (auto [id, val] : know)ask[id] = val;
      |                   ^
cave.cpp:37:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |             for (auto [id, val] : know)ask[id] = val;
      |                       ^

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