Submission #784731

#	Time	Username	Problem	Language	Result	Execution time	Memory
784731		bane	Cave (IOI13_cave)	C++17	0 / 100	974 ms	484 KiB

cave

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

using namespace std;

void exploreCave(int N) {
    /* ... */
    
    vector<int>ne_najdeni; // SWITCHOVI KOI NE SE DOZNAENI
    vector<int>najdeni; // SWITCHOVI KOI SE DOZNAENI

    int Match[N]; // SWITCH - > VRATA
    int P[N]; // SOSTOJBA NA SWITCH
    for (int i = 0; i < N; i++){
        ne_najdeni.push_back(i);
    }

    for (int i = 0; i < N; i++){
        //PROBUVAME DA JA OTVORIME I-TATA VRATA
        int S[N];
        for (int j : najdeni){
            S[j] = P[j];
        }
        //SEGA SME GI OTVORILE SITE VRATI PRED I

        for (int j : ne_najdeni){
            S[j] = 1;
        }
        

        int key = 1;

        int resp = tryCombination(S);
        if (resp == i){
            //ovaa vrata e seuste zaklucena, znaci se otklucuva so 0
            key ^= 1;
            for (int j : ne_najdeni){
                S[j] = key;
            }
        }

        int l = 0, r = (int)ne_najdeni.size() - 1;
        while(l<=r){
            int mid = (l+r) / 2;
            
            for (int j = 0 ; j < mid; j++){
                S[ne_najdeni[j]] = !key;
            }
            for (int j = mid; j < (int)ne_najdeni.size(); j++){
                S[ne_najdeni[j]] = key;
            }

            resp = tryCombination(S);
            if (resp == i){
                //zaklucena e seuste
                //prosiri
                r = mid - 1;
            }else{
                //otklucena e
                l = mid + 1;//zatesni
            }
        }
        P[l-1]=key;
        najdeni.push_back(l-1);
        sort(najdeni.begin(),najdeni.end());
        Match[l-1]=i;
        vector<int>nov;
        for (int j : ne_najdeni){
            if (j == l - 1)continue;
            nov.push_back(j);
        }
        ne_najdeni = nov;
        sort(ne_najdeni.begin(),ne_najdeni.end());
    }
    answer(P,Match);
}

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