Submission #1216814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216814		lizi14	Cave (IOI13_cave)	C++20	0 / 100	165 ms	528 KiB

cave

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include "cave.h"
 
using namespace std;

void exploreCave(int N) {
    int x[N];
    fill(x,x+N,1);
    int s[N];
    fill(s,s+N,0);
    int an=0;
    int f=0;
    int c[N];
    int h=0;
    
    while(h<N){
        int a=tryCombination(x);
        // if(a==-1){
        //     break;
        // }
        if(a>h || a==-1){
            
            int ans=0;
            int l=0,r=N-1;
            while(l<r){
               int mid=(l+r)/2;
               for(int i=l; i<mid; i++){
                   if(s[i]==0){
                       x[i]=1-x[i];
                   }
               }
               int k=tryCombination(x);
               if(k==h+1){
                   l=mid+1;
                   ans=mid;
               }
               else r=mid-1;
            }
            an=a;
            //x[ans]=1-x[ans];
            s[ans]=1;
            c[ans]=h;
            for(int i=0; i<N; i++){
                if(s[i]==0){
                    x[i]=0;
                }
            }
            h++;
        }
        else{
            for(int i=0; i<N; i++){
                if(s[i]==0){
                    x[i]=1-x[i];
                    //f=x[i];
                }
            }
        }
        // for(int i=0; i<N; i++){
        //     cout<<x[i]<<" ";
        // }
        // cout<<endl;
        
        //x[a]=1-x[a];
    }
    
    return answer(x, c);
}
 

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