Submission #256250

#	Time	Username	Problem	Language	Result	Execution time	Memory
256250		Sorting	Cave (IOI13_cave)	C++17	100 / 100	675 ms	916 KiB

cave

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

using namespace std;

const int k_N = 5000 + 3;

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

int s[k_N], d[k_N];
vector<int> curr;

void exploreCave(int n){
    for(int i = 0; i < n; ++i)
        curr.push_back(i);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < curr.size(); ++j)
            s[curr[j]] = 0;

        int q1 = tryCombination(s);
        if(q1 == -1) q1 = n;

        int l = 0, r = (int)curr.size() - 1;
        while(l != r){
            int mid = (l + r) >> 1;
            for(int j = 0; j <= mid; ++j)
                s[curr[j]] = !(q1 > i);
            for(int j = mid + 1; j < curr.size(); ++j)
                s[curr[j]] = (q1 > i);

            int q2 = tryCombination(s);
            if(q2 == -1) q2 = n;

            if(q2 > i) r = mid;
            else l = mid + 1;
        }

        d[curr[l]] = i;
        s[curr[l]] = !(q1 > i);

        curr.erase(curr.begin() + l);
    }

    answer(s, d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:19:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < curr.size(); ++j)
                        ~~^~~~~~~~~~~~~
cave.cpp:30:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = mid + 1; j < curr.size(); ++j)
                                  ~~^~~~~~~~~~~~~

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