Submission #548386

#	Time	Username	Problem	Language	Result	Execution time	Memory
548386		chirathnirodha	동굴 (IOI13_cave)	C++17	100 / 100	443 ms	588 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
 
int n;
int matched[5010];
int door[5010];
int det[5010][3];
bool fp=false;
int mc=0;
void foundpath(int arr[]){
    for(int i=0;i<n;i++){
        if(matched[i]==-1){
            matched[i]=arr[i];
            arr[i]=(arr[i]+1)%2;
            int val=tryCombination(arr);
            door[i]=val;
            arr[i]=(arr[i]+1)%2;
        }
    }
    return;
}
void calc(int x){
    if(fp==true || mc==n)return;
    int a=det[x][0],b,c;
    int arr[n];
    while(true){
        b=det[x][1],c=det[x][2];
        if(b==c){
            matched[b]=a;
            door[b]=x;
            mc++;
            return;
        }
        for(int i=0;i<n;i++){
            if(matched[i]!=-1)arr[i]=matched[i];
            else arr[i]=0;
        }
        for(int i=b;i<=(b+c)/2;i++)if(matched[i]==-1)arr[i]=1;
        int val=tryCombination(arr);
        if(val==-1){
            foundpath(arr);
            fp=true;
            return;
        }
        if(a==1){
            if(val>x)det[x][2]=(b+c)/2;
            else if(val==x)det[x][1]=(b+c)/2+1;
            else {  
                det[val][0]=0;
                det[val][1]=b;
                det[val][2]=(b+c)/2;
                calc(val);
            }
        }
        else{
            if(val>x)det[x][1]=(b+c)/2+1;
            else if(val==x)det[x][2]=(b+c)/2;
            else {  
                det[val][0]=1;
                det[val][1]=(b+c)/2+1;
                det[val][2]=c;
                calc(val);
            }
        }
    }
    return;
}
void exploreCave(int N) {
   n=N;
   for(int i=0;i<n;i++){
       matched[i]=door[i]=-1;
       det[i][0]=-1;
       det[i][1]=0;det[i][2]=n-1;
   }
   int arr[n];memset(arr,0,sizeof(arr));
   while(true){
       for(int i=0;i<n;i++)if(matched[i]!=-1)arr[i]=matched[i];
       int val=tryCombination(arr);
       if(val==-1){foundpath(arr);break;}
       det[val][0]=1;
       calc(val);
   }
   int S[n];
   int D[n];
   for(int i=0;i<n;i++){S[i]=matched[i];D[i]=door[i];}
   answer(S,D);
   return;
}

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