Submission #719947

#	Time	Username	Problem	Language	Result	Execution time	Memory
719947		Yell0	Cave (IOI13_cave)	C++17	0 / 100	2065 ms	596 KiB

cave

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "cave.h"
 
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void exploreCave(int N) { // -1
  int config[N],perm[N];
  ordered_set idx;
  for(int i=0;i<N;++i) idx.insert(i);
  for(int i=0;i<N;++i) {
    bool on=1;
    for(int x:idx) config[x]=1;
    if(tryCombination(config)==i) on=0;
    for(int x:idx) config[x]=!on;
    if(i==N-1) {
      perm[*idx.find_by_order(0)]=i;
      config[*idx.find_by_order(0)]=on;
      break;
    }
    int st=0,sz=(N-i)/2,pst=0,psz=N-i,sw=st;
    while(sz>0) {
      for(int j=st;j<st+sz;++j) config[*idx.find_by_order(j)]=on;
      //cout<<st<<' '<<sz<<'\n';
      //for(int i=0;i<N;++i) cout<<config[i]<<" \n"[i==N-1];
      //cout<<tryCombination(config)<<'\n'<<'\n';
      if(tryCombination(config)==i) {
        pst=st;
        st=st+sz;
        int tsz=sz;
        sz=(psz-sz)/2;
        psz=tsz;
      } else sz/=2;
      sw=*idx.find_by_order(st);
      for(int j=pst;j<pst+psz;++j) config[*idx.find_by_order(j)]=!on;
    }

    perm[sw]=i;
    config[sw]=on;
    idx.erase(sw);
    //for(int x:idx) cout<<x<<'\n';
  }
  answer(perm,config);
}

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