제출 #1310706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310706		lizi14	동굴 (IOI13_cave)	C++20	100 / 100	296 ms	520 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave(int N) {
    int x[N];
    fill(x,x+N,0);
    int s[N];
    fill(s,s+N,0);
    int an=0;
    int f=0;
    int c[N];
    fill(c,c+N,0);
    int h=0;
    
    for(int h=0; h<N; h++){
        for(int i=0; i<N; i++){
            if(c[i]==0)x[i]=0;
        }
        int a=tryCombination(x);
        int ka;
        if(a!=h){
            ka=0;
        }
        else{
            ka=1;
        }
        for(int i=0; i<N; i++){
            if(c[i]==0)x[i]=1-ka;
        }
        //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(c[i]==0){
                       x[i]=ka;
                   }
               }
               int a=tryCombination(x);
               if(a!=h){
                   r=mid;
                   ans=mid;
               }
               else {
                   ans=mid+1;
                   l=mid+1;
               }
               for(int i=l; i<=mid; i++){
                   if(c[i]==0)x[i]=1-ka;
               }
            }
            //an=a;
            //x[ans]=1-x[ans];
            s[ans]=h;
            x[ans]=ka;
            c[ans]=1;
            // for(int i=0; i<N; i++){
            //     if(s[i]==0){
            //         x[i]=0;
            //     }
            // }
           
        //}
        // 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, s);
}
 

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