Submission #757716

#	Time	Username	Problem	Language	Result	Execution time	Memory
757716		Piokemon	Cave (IOI13_cave)	C++17	100 / 100	540 ms	588 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void exploreCave(int N) {
    int komb[N];
    int drzwi[N];
    int S[N];
    for (int x=0;x<N;x++){
        komb[x]= -1;
        drzwi[x] = -1;
    }
    int res;
    for (int x=0;x<N;x++){
        for (int y=0;y<N;y++){
            if (komb[y]==-1) S[y] = 1;
            else S[y] = komb[y];
        }
        res = tryCombination(S);
        int dobre;
        if (res>x || res==-1)dobre = 1;
        else dobre = 0;
        int pocz,kon,srod;
        vector<int> zost;
        zost.clear();
        for (int y=0;y<N;y++){
            if (komb[y]==-1) zost.push_back(y);
        }
        pocz = 0;
        kon = zost.size()-1;
        while(pocz<kon){
            srod = (pocz+kon)/2;
            for (int y=0;y<N;y++){
                if (komb[y]==-1) S[y] = 1-dobre;
                else S[y] = komb[y];
            }
            for (int y=pocz;y<=srod;y++) S[zost[y]] = dobre;
            res = tryCombination(S);
            /*cout << x << ' ' << res << '\n';
            for (int y=0;y<N;y++) cout << S[y] << ' ';
            cout << '\n';*/
            if (res>x || res==-1) kon = srod;
            else pocz = srod+1;
        }
        komb[zost[pocz]] = dobre;
        drzwi[zost[pocz]] = x;
    }
    answer(komb,drzwi);
    return;
}

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