Submission #519256

#	Time	Username	Problem	Language	Result	Execution time	Memory
519256		Jomnoi	Cave (IOI13_cave)	C++17	100 / 100	578 ms	696 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define DEBUG 0
using namespace std;

const int MX = 5e3 + 10;

int S[MX], D[MX], res, res1;
bool up;
int l, r, pos;
vector <int> vec, tmp;

void exploreCave(int N) {    
    for(int i = 0; i < N; i++) {
        vec.push_back(i);
    }
    for(int i = 0; i < N; i++) {
        for(auto v : vec) {
            S[v] = 0;
        }

        res1 = tryCombination(S);
        up = (res1 == i);
        l = 0, r = vec.size() - 1, pos = -1;
        while(l <= r) {
            int mid = (l + r) / 2;

            for(int j = 0; j <= mid; j++) {
                S[vec[j]] = up;
            }
            for(int j = mid + 1; j < vec.size(); j++) {
                S[vec[j]] = up ^ 1;
            }

            if(tryCombination(S) == i) {
                l = mid + 1;
            }
            else {
                pos = mid;
                r = mid - 1;
            }
        }

        S[vec[pos]] = up;
        D[vec[pos]] = i;
        tmp.clear();
        for(int j = 0; j < pos; j++) {
            tmp.push_back(vec[j]);
        }
        for(int j = pos + 1; j < vec.size(); j++) {
            tmp.push_back(vec[j]);
        }
        vec = tmp;
    }
    answer(S, D);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:31:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(int j = mid + 1; j < vec.size(); j++) {
      |                                  ~~^~~~~~~~~~~~
cave.cpp:50:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j = pos + 1; j < vec.size(); j++) {
      |                              ~~^~~~~~~~~~~~

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