Submission #624943

#	Time	Username	Problem	Language	Result	Execution time	Memory
624943		Mr_Husanboy	Cave (IOI13_cave)	C++14	100 / 100	288 ms	460 KiB

cave

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

using namespace std;



void exploreCave(int N) {
    int n = N;
    vector<int> done(N), ans(N), door(N);
    for(int i = 0; i < n; i ++){
        int k = tryCombination(ans.data());
     //   cout << k << endl;
        if(k == i){
            int l = 0, r = n - 1;
            while(l != r){
                int m = (l+r)/2;
                for(int j = l; j <= m; j ++){
                    if(!done[j]) ans[j] = 1;
                }
                int tem = tryCombination(ans.data());
                for(int j = l; j <= m; j ++){
                    if(!done[j]) ans[j] = 0;
                }
                if(tem == -1) tem = n;
                if(tem > i){
                    r = m;
                }else l = m + 1;
            }
            door[r] = i;
            done[r] = 1;
            ans[r] = 1;
      //      cout << r << " r2" << endl;
        }else{
            int l = 0, r = n - 1;
            while(l != r){
                int m = (l+r)/2;
                for(int j = l; j <= m; j ++){
                    if(!done[j]) ans[j] = 1;
                }
                int tem = tryCombination(ans.data());
                for(int j = l; j <= m; j ++){
                    if(!done[j]) ans[j] = 0;
                }
                if(tem == -1) tem = n;
                if(tem == i){
                    r = m;
                }else l = m + 1;

            } //cout << r << "r1 " << endl;
            door[r] = i;
            done[r] = 1;
            ans[r] = 0;
            //ans[r] = 0; cout << ans[r] << endl;
        }
    }
  //  for(auto u : ans) cout << u << ' ' ; cout << endl;
   // for(auto u : door) cout << u << ' ' ; cout << endl;
    answer(ans.data(), door.data());
}

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