Submission #908333

#	Time	Username	Problem	Language	Result	Execution time	Memory
908333		tosivanmak	Cave (IOI13_cave)	C++17	0 / 100	9 ms	604 KiB

cave

#include<bits/stdc++.h>
using namespace std;
#define ll long long


#ifdef __cplusplus
extern "C" {
#endif
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#ifdef __cplusplus
}
#endif
vector<ll>cur;
int a[5005];
bool canuse[5005];
bool open[5005];
int refdoor[5005];
// TODO: global variables can be declared here

int ck(ll l, ll r){
    for(int i=l;i<=r;i++){
        a[i]^=1;
    }
    int lol=tryCombination(a);
    for(int i=l;i<=r;i++){
        a[i]^=1;
        }
    return lol;
}
void get(ll id){
    ll l=0,r=cur.size()-1;
    int compare=ck(l,r);
    while(l<=r){
        if(l==r){
            break;
        }
        else if(l==r-1){
            if(ck(l,l)!=compare){
                r=l;
            }
            else{
                l=r;
            }
            break;
        }
        else{
            ll mid=(l+r)>>1;
            if(ck(l,mid)!=compare){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
    }
    if(compare==id){
        open[l]=0;
        a[id]=0;
    }
    else{
        open[l]=1;
        a[id]=1;
    }
    refdoor[l]=id;
    canuse[l]=0;
}
void exploreCave(int N) {
  // TODO: implementation
    int n=N;
    for(int i=0;i<n;i++){
        a[i]=1;
        cur.push_back(i);
    }
  tryCombination(a);
  for(int i=0;i<n;i++){
      get(i);
      cur.clear();
      for(int j=0;j<n;j++){
          if(canuse[j]){
              cur.push_back(j);
          }
      }
  }
    int state[n],ref[n];
    for(int i=0;i<n;i++){
        state[i]=open[i];
        ref[i]=refdoor[i];
    }
    answer(state,ref);
}

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