Submission #719933

#	Time	Username	Problem	Language	Result	Execution time	Memory
719933		Yell0	Cave (IOI13_cave)	C++17	0 / 100	1146 ms	644 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) {
  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;
    int st=0,sz=(N-i)/2,psz=N-i,sw;
    while(sz>0) {
      sw=st;
      for(int j=st;j<=st+sz;++j) config[*idx.find_by_order(j)]=on;
      if(tryCombination(config)<=i) {
        st=st+sz;
        int tsz=sz;
        sz=(psz-sz)/2;
        psz=tsz;
      } else {
        sz/=2;
        sw=st;
      }
      for(int j=st;j<=st+sz;++j) config[*idx.find_by_order(j)]=!on;
    }
    perm[sw]=i;
    config[sw]=on;
    idx.erase(sw);
  }
  answer(perm,config);
}

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