Submission #1071637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071637		TsotneSV	Cave (IOI13_cave)	C++14	0 / 100	1 ms	1116 KiB

cave

#include <bits/stdc++.h>

#include "cave.h"
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/

#define pb push_back
#define ins insert
#define sz(x) ((long long) (x).size())
#define dbg(x) cerr<<#x<<" "<<x<<endl


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

void exploreCave(int N) {
    
    int S[N],D[N]; memset(S,0,sizeof(S)); int curr = tryCombination(S);

    vector<int> idx; for(int i=0;i<N;i++) idx.pb(i);

    while(idx.size() and curr != N) {

        int l = 0,r = sz(idx)-1,id = sz(idx);

        while(l <= r) {

            int m = (l + r)/2;

            for(int i=0;i<=m;i++) S[idx[i]] = 1;
            
            int x = tryCombination(S);

            if(x != curr) {
                id = m;
                r = m - 1;
            }else {
                l = m + 1;
            }

            for(int i=0;i<=m;i++) S[idx[i]] = 0;

        }

        for(int i=0;i<=id;i++) S[idx[i]] = 1;

        int x = tryCombination(S);

        for(int i=0;i<=id;i++) S[idx[i]] = 0;

        if(x != -1 and x < curr) {
            D[idx[id]] = x;  
        } else {
            D[idx[id]] = curr + 1;
            S[idx[id]] = 1;
            curr++; 
        } 
        
        idx.erase(idx.begin()+id);

    } 

    answer(S,D);

}

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