Submission #578844

#	Time	Username	Problem	Language	Result	Execution time	Memory
578844		enerelt14	Cave (IOI13_cave)	C++17	0 / 100	551 ms	460 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n, s[5000], d[5000], re[5000], ans[5000];
bool is;
void find(int x, int l, int r){
    if (l==r){
        d[l]=x;
        re[x]=l;
        if (tryCombination(s)==x)ans[l]=1-s[l];
        else ans[l]=s[l];
        return;
    }
    int mid=(l+r)/2;
    for (int i=l;i<=mid;i++)s[i]=1-s[i];
    for (int j=0;j<x;j++)s[re[j]]=ans[re[j]];
    if (tryCombination(s)==x){
        if (is)find(x, mid+1, r);
        else{
            is=1;
            find(x, l, mid);
        }
    }
    else{
        if (is){
            is=0;
            find(x, l, mid);
        }
        else find(x, mid+1, r);
    }
}
void exploreCave(int N) {
    n=N;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++)s[j]=0;
        for (int j=0;j<i;j++)s[re[j]]=ans[re[j]];
        if (tryCombination(s)==i)is=1;
        else is=0;
        find(i, 1, n);
    }
    answer(ans, d);
}

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