Submission #1208561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208561		pera	Cave (IOI13_cave)	C++20	13 / 100	194 ms	131072 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;
   while(true){
      u = tryCombination(W);
      if(u == -1){
         break;
      }
      vector<int> v;
      for(int i = 0;i < N;i ++){
         if(W[i] == 0){
            v.emplace_back(i);
         }
      }
      auto assign = [&](vector<int> &a){
         if(a.empty()){
            return false;
         }
         for(int x : a){
            W[x] = 1;
         }
         int A = tryCombination(W);
         for(int x : a){
            W[x] = 0;
         }
         return (A != u);
      }; 
      function<int(vector<int>&)> solve = [&](vector<int> &a){
         if((int)a.size() == 1){
            return a[0];
         }
         vector<int> L , R;
         for(int i = 0;i < (int)a.size();i ++){
            if(i < (int)a.size() / 2){
               L.push_back(a[i]);
            }else{
               R.push_back(a[i]);
            }
         }
         if(assign(L)){
            return solve(L);
         }
         return solve(R);
      };
      int p = solve(v);
      S[p] = W[p] = 1;
      D[p] = u;
   }
   for(int i = 0;i < N;i ++){
      W[i] = 1;
   }
   while(true){
      u = tryCombination(W);
      if(u == -1){
         break;
      }
      vector<int> v;
      for(int i = 0;i < N;i ++){
         if(W[i] == 1 && !S[i]){
            v.emplace_back(i);
         }
      }
      auto assign = [&](vector<int> &a){
         if(a.empty()){
            return false;
         }
         for(int x : a){
            W[x] = 0;
         }
         int A = tryCombination(W);
         for(int x : a){
            W[x] = 1;
         }
         return (A != u);
      }; 
      function<int(vector<int>&)> solve = [&](vector<int> &a){
         if((int)a.size() == 1){
            return a[0];
         }
         vector<int> L , R;
         for(int i = 0;i < (int)a.size();i ++){
            if(i < (int)a.size() / 2){
               L.push_back(a[i]);
            }else{
               R.push_back(a[i]);
            }
         }
         if(assign(L)){
            return solve(L);
         }
         return solve(R);
      };
      int p = solve(v);
      S[p] = W[p] = 0;
      D[p] = 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