Submission #230061

#	Time	Username	Problem	Language	Result	Execution time	Memory
230061		chubyxdxd	Cave (IOI13_cave)	C++11	100 / 100	437 ms	632 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define test tryCombination
using namespace std;
void exploreCave(int N) {
  int door[N],ans[N],vis[N];
  for(int i=0;i<N;i++){
    ans[i]=1;
    door[i]=-1;
    vis[i]=1;
  }
  //int curr=test(ans);
  // cout<<curr<<endl;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(vis[j]==1)ans[j]=1;
    }
    int h=test(ans);
    int sw=0;
    if(h==i){
      sw=1;
    }
    //cout<<"gg=="<<sw<<endl;
    for(int j=0;j<N;j++){
      if(vis[j]==1)ans[j]=sw;
    }
    int lo=0,hi=N-1,r;
    while(lo<hi){
      int mid=(lo+hi)/2;
      for(int j=lo;j<=mid;j++){
	if(vis[j]==1)ans[j]=sw;
      }
      for(int j=mid+1;j<=hi;j++){
	if(vis[j]==1)ans[j]=(sw^1);
      }
      r=test(ans);
      //cout<<r<<endl;
      if(r==i){
	hi=mid;
      }
      else{
	lo=mid+1;
      }
      //cout<<lo<<" "<<hi<<endl; 
    }
    door[lo]=i;
    vis[lo]=-1;
    ans[lo]=(sw^1);
    /*
    cout<<lo<<" -< "<<endl;
    cout<<"swich"<<endl;
    for(int j=0;j<N;j++){
      cout<<ans[j]<<" ";
    }
    cout<<endl;
    cout<<"door"<<endl;
    for(int j=0;j<N;j++){
      cout<<door[j]<<" ";
    }
    cout<<endl;
    cout<<"off"<<endl;
    for(int j=0;j<N;j++){
      cout<<vis[j]<<" ";
    }
    cout<<endl;*/
  }
  answer(ans,door);
}

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