Submission #1265952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265952		uzukishinobu	Cave (IOI13_cave)	C++20	100 / 100	430 ms	604 KiB

cave

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

vector <int> v;
int a;
int ask(vector <int> p){
    int p1[a];
    for (int i=0;i<a;i++){
         p1[i]=p[i];
    }
    return tryCombination(p1);
}
bool check[1000005];
int val[1000005];
void exploreCave(int n) {
    int ans[n]={0};
    int ans1[n]={0};
    v.resize(n);
    a=n;
    for (int i=0;i<n;i++){
        v[i]=0;
    }
//    v[2]=1;
//    cout << ask(v) << "\n";
    for (int i=0;i<a;i++){
         int pre=ask(v);
//         cout << pre << " " << "\n";
//         for (int i=0;i<a;i++){
//              cout << v[i] << " ";
//         }
//         cout << "\n";

         if (pre>i || pre==-1){
             int pre1=0;
             int l=0;
             int r=a-1;
             int pos=a-1;
             while (l<=r){
                  int mid=(l+r)/2;
                  vector <int> p=v;
                  for (int j=0;j<=mid;j++){
                       if (!check[j]){
                           p[j]=1;
                       }
                  }
                  int sad=ask(p);
                  if (sad<=i && sad!=-1){
                      pos=mid;
                      r=mid-1;
                  }else{
                      l=mid+1;
                  }
             }
//             cout << pos << "\n";
             ans[pos]=pre1;
             ans1[pos]=i;
             v[pos]=pre1;
             check[pos]=1;
         }else{
             int pre1=1;
             int l=0;
             int r=a-1;
             int pos=a;
             while (l<=r){
                  int mid=(l+r)/2;
                  vector <int> p=v;
                  for (int j=0;j<=mid;j++){
                       if (!check[j]){
                           p[j]=1;
                       }
                  }
                  int sad=ask(p);
                  if (sad>i || sad==-1){
                      pos=mid;
                      r=mid-1;
//                      if (i==0){
//                         cout << mid << "\n";
//                      }
                  }else{
                      l=mid+1;
                  }
             }
//             cout << pos << "\n";
             ans[pos]=pre1;
             ans1[pos]=i;
             v[pos]=pre1;
             check[pos]=1;
         }
    }
//          for (int i=0;i<a;i++){
//              cout << v[i] << " ";
//         }
//         cout << "\n";
    answer(ans,ans1);
}

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