Submission #908440

#	Time	Username	Problem	Language	Result	Execution time	Memory
908440		tosivanmak	Cave (IOI13_cave)	C++17	0 / 100	167 ms	1104 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

// int N;
// int realS[5005],realD[5005],inv[5005];
// void answer(int S[], int D[]) {
//     int i;
//     int correct = 1;
//     for (i = 0; i < N; ++i){
//         if (S[i] != realS[i] || D[i] != realD[i]) {
//             correct = 0;
//             break;
//         }
//     }

//     if (correct){
//        cout<<"CORRECT\n";
//     }
//     else{
//        cout<<"INCORRECT\n";
//     }
//     for (i = 0; i < N; ++i) {
//         cout<<S[i]<<" ";
//     }
//    cout<<'\n';

//     for (i = 0; i < N; ++i) {
//         cout<<D[i]<<" ";
//     }
//     cout<<'\n';
// }

// int tryCombination(int S[]) {
//     int i;
//     for (i = 0; i < N; i++){
//         if (S[inv[i]] != realS[inv[i]]){
//             // cout<<S[inv[i]]<<" "<<realS[inv[i]]<<"\n";
//             return i;
//         }
//     }
//     return -1;
// }
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(1,0);
    cout<<compare<<'\n';
    while(l<=r){
        if(l==r){
            break;
        }
        else if(l==r-1){
          ll uiuiu=ck(l,l);
          cout<<l<<" "<<l<<" "<<uiuiu<<'\n';
            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);
            cout<<l<<" "<<mid<<" "<<uiuiu<<'\n';
            if((compare==id&&uiuiu!=compare) or (uiuiu==id&&uiuiu!=compare)){
                r=mid;
            }
            else{
               l=mid+1;
            }
        }
    }
    if(compare==id){
        open[cur[l]]=0;
        a[cur[l]]=0;
    }
    else{
        open[cur[l]]=1;
        a[cur[l]]=1;
    }
    refdoor[cur[l]]=id;
    canuse[cur[l]]=0;
}
void exploreCave(int N) {
  // TODO: implementation
    int n=N;
    for(int i=0;i<n;i++){
        a[i]=1;
        canuse[i]=1;
        cur.push_back(i);
    }
  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);
          }
      }
    //   for(auto& u: cur){
    //       cout<<u<<" ";
    //   }
    //   cout<<"\n\n\n\n\n";
  }
    int state[n],ref[n];
    for(int i=0;i<n;i++){
        state[i]=open[i];
        // cout<<state[i]<<" ";
        ref[i]=refdoor[i];
    }
    // for(int i=0;i<n;i++){
    //     cout<<ref[i]<<" ";
    // }
    answer(state,ref);
}

// int main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     cin>>N;
//     for(int i=0;i<N;i++){
//         cin>>realS[i];
//     }
//     for(int i=0;i<N;i++){
//         cin>>realD[i];
//         inv[realD[i]]=i;
//     }
//     exploreCave(N);
// }

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