Submission #598153

#	Time	Username	Problem	Language	Result	Execution time	Memory
598153		Jarif_Rahman	Cave (IOI13_cave)	C++17	21 / 100	72 ms	65536 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int TryCombination(vector<int> s){
    int n = s.size();
    int* S = new int[n];

    for(int i = 0; i < n; i++) S[i] = s[i];
    return tryCombination(S);
}

void Answer(vector<int> s, vector<int> d){
    int n = s.size();
    int* S = new int[n];
    int* D = new int[n];

    for(int i = 0; i < n; i++) S[i] = s[i], D[i] = d[i];
    answer(S, D);
}

void exploreCave(int n){
    int ls = -1;

    vector<int> tbc(n);
    vector<int> cur(n, 0);
    vector<int> door(n, -1);

    for(int i = 0; i < n; i++) tbc[i] = i;

    while(tbc.size() > 0){
        int a = 0, b = tbc.size(); b--;
        int def = TryCombination(cur);
        if(def == -1) def = n;
        while(a < b){
            int md = (a+b)/2;
            auto _cur = cur;
            for(int i = 0; i <= md; i++) _cur[tbc[i]] = !_cur[tbc[i]];
            if(TryCombination(_cur) == def) a = md+1;
            else b = md;
        }
        int x = tbc[a];
        tbc.erase(tbc.begin()+a);
        cur[x] = !cur[x];
        int nxt = TryCombination(cur);
        if(nxt == -1) nxt = n;
        if(nxt > def) door[x] = def;
        else door[x] = nxt, cur[x] = !cur[x];
    }

    Answer(cur, door);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:28:9: warning: unused variable 'ls' [-Wunused-variable]
   28 |     int ls = -1;
      |         ^~

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