Submission #548216

#	Time	Username	Problem	Language	Result	Execution time	Memory
548216		chirathnirodha	Cave (IOI13_cave)	C++17	0 / 100	97 ms	65536 KiB

cave

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

int n;
int nt=0;
int trycom[70001][5000];
int resu[70001];
int matched[5000];
int door[5000];
int det[5000][3];
bool fp=false;
void foundpath(int x){
    int arr[n];
    for(int i=0;i<n;i++)arr[i]=trycom[x][i];
    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)return;
    int a=det[x][0],b=det[x][1],c=det[x][2];
    if(b==c){
        matched[b]=(trycom[a][b]+1)%2;
        door[b]=x;
        return;
    }
    int arr[n];
    for(int i=0;i<n;i++){
        if(matched[i]!=-1)arr[i]=matched[i];
        else arr[i]=trycom[a][i];
    }
    for(int i=b;i<=(b+c)/2;i++)if(matched[i]==-1)arr[i]=(arr[i]+1)%2;
    for(int i=0;i<n;i++)trycom[nt][i]=arr[i];

    int val=tryCombination(arr);
    resu[nt]=val;
    if(val==-1){
        foundpath(nt);
        fp=true;
        return;
    }
    else if(val>x){
        det[x][0]=nt;
        det[x][2]=(b+c)/2;
        calc(x);
    }
    else if(val==x){
        det[x][0]=nt;
        det[x][1]=(b+c)/2+1;
        calc(x);
    }
    else {  
        det[val][0]=nt;
        det[val][1]=b;
        det[val][2]=(b+c)/2;
        calc(val);
        calc(x);
    }
    nt++;
    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;
   }
   for(int i=0;i<n;i++)trycom[nt][i]=0;
   nt++;
   det[n-1][0]=0;
   calc(n-1);
   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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24