Submission #1075410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075410		Ignut	Cave (IOI13_cave)	C++17	100 / 100	181 ms	856 KiB

cave

// Ignut

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

using namespace std;

int tryCombination(int S[]);

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

int NN;

int Ask(int S[]) {
    int ask = tryCombination(S);
    if (ask == -1) return NN;
    return ask;
}

void exploreCave(int N) {
    NN = N;
    int door[N];
    int sw[N] = {};
    vector<int> possible;
    for (int i = 0; i < N; i ++) possible.push_back(i);
    bool used[N] = {};

    int cntKnow = 0;

    while (cntKnow < N) {
        int ask0 = Ask(sw);
        /*if (ask == -1) {
            cntKnow = N; break;
        }*/
        // cout << cntKnow << " : " << ask0 << '\n';
        // for (int val : possible) cout << val << '_';
        // cout << '\n';

        if (ask0 == cntKnow) {
            // nextVal is 1
            int lo = 0, hi = possible.size() - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                for (int i = lo; i <= mid; i ++) sw[possible[i]] ^= 1;
                int ask = Ask(sw);
                // cout << " -- " << mid << " -- " << ask << '\n';
                for (int i = lo; i <= mid; i ++) sw[possible[i]] ^= 1;
                if (ask == ask0)
                    lo = mid + 1;
                else
                    hi = mid;
            }
            
            sw[possible[lo]] ^= 1;
            door[possible[lo]] = cntKnow;
            vector<int> next_possible;
            for (int i = 0; i < possible.size(); i ++) if (i != lo) next_possible.push_back(possible[i]);
            possible = next_possible;
        }
        else {
            // nextVal is 0
            int lo = 0, hi = possible.size() - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                for (int i = lo; i <= mid; i ++) sw[possible[i]] ^= 1;
                int ask = Ask(sw);
                for (int i = lo; i <= mid; i ++) sw[possible[i]] ^= 1;
                if (ask == cntKnow)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            door[possible[lo]] = cntKnow;
            vector<int> next_possible;
            for (int i = 0; i < possible.size(); i ++) if (i != lo) next_possible.push_back(possible[i]);
            possible = next_possible;
        }

        cntKnow ++;
    }

    // for (int i = 0; i < N; i ++) sw[i] ^= 1;    
    answer(sw, door);
    return;
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int i = 0; i < possible.size(); i ++) if (i != lo) next_possible.push_back(possible[i]);
      |                             ~~^~~~~~~~~~~~~~~~~
cave.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (int i = 0; i < possible.size(); i ++) if (i != lo) next_possible.push_back(possible[i]);
      |                             ~~^~~~~~~~~~~~~~~~~
cave.cpp:26:10: warning: unused variable 'used' [-Wunused-variable]
   26 |     bool used[N] = {};
      |          ^~~~

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