Submission #1208596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208596		pera	Cave (IOI13_cave)	C++20	13 / 100	201 ms	612 KiB

cave

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

void exploreCave(int N) {
   int S[N] , D[N] , W[N];
   memset(S , 0 , sizeof(S));
   memset(W , 0 , sizeof(W));
   int u;
   vector<int> v;
   for(int i = 0;i < N;i ++){
      v.push_back(i);
   }
   int C = 0;
   vector<int> nv;
   while(true){
      u = tryCombination(W);
      if(u == -1){
         break;
      }
      ++C;
      assert(C <= N);
      auto assign = [&](int m){
         for(int i = 0;i <= m;i ++){
            W[v[i]] = 1;
         }
         int A = tryCombination(W);
         for(int i = 0;i <= m;i ++){
            W[v[i]] = 0;
         }
         return (A != u);
      }; 
      int l = 0 , r = (int)v.size() - 1 , ans = -1 , c = 0;
      while(l <= r){
         int m = (l + r) / 2;
         ++c;
         if(assign(m)){
            ans = m;
            r = m - 1;
         }else{
            l = m + 1;
         }
      }
      assert((1 << (c + 1)) > (int)v.size());
      ans = v[ans];
      for(int x : v){
         if(x != ans){
            nv.emplace_back(x);
         }
      }
      v = nv;
      vector<int>().swap(nv);
      S[ans] = W[ans] = 1;
      D[ans] = u;
   }
   for(int i = 0;i < N;i ++){
      W[i] = 1;
   }
   while(!v.empty()){
      ++C;
      assert(C <= N);
      int u = tryCombination(W);
      auto assign = [&](int m){
         for(int i = 0;i <= m;i ++){
            W[v[i]] = 0;
         }
         int A = tryCombination(W);
         for(int i = 0;i <= m;i ++){
            W[v[i]] = 1;
         }
         return (A != u);
      }; 
      int l = 0 , r = (int)v.size() - 1 , ans , c = 0;
      while(l <= r){
         int m = (l + r) / 2;
         ++c;
         if(assign(m)){
            ans = m;
            r = m - 1;
         }else{
            l = m + 1;
         }
      }
      assert((1 << (c + 1)) > (int)v.size());
      ans = v[ans];
      for(int x : v){
         if(x != ans){
            nv.emplace_back(x);
         }
      }
      v = nv;
      vector<int>().swap(nv);
      S[ans] = W[ans] = 0;
      D[ans] = u;
   }
   answer(S , D);
   return;
}

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