Submission #908362

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

cave

#include<bits/stdc++.h>
#include "cave.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[cur[i]]^=1;
    }
    int lol=tryCombination(a);
    for(int i=l;i<=r;i++){
        a[cur[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){
          ll uiuiu=ck(l,l);
            if((compare==id&&uiuiu!=compare) or (uiuiu==id&&uiuiu!=compare)){
                r=l;
            }
            else{
                l=r;
            }
            break;
        }
        else{
            ll mid=(l+r)>>1;
            int uiuiu=ck(l,mid);
            if((compare==id&&uiuiu!=compare) or (uiuiu==id&&uiuiu!=compare)){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
    }
    if(compare==id){
        open[l]=0;
        a[l]=0;
    }
    else{
        open[l]=1;
        a[l]=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