Submission #1177503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177503		tegshzaya	Cave (IOI13_cave)	C++20	100 / 100	488 ms	624 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
	int n,a[5005],b[5005],c[5005];
void exploreCave(int N) {
    n=N;
    for(int i=0;i<n;i++){
        int s[n];
        for(int j=0;j<n;j++){
            if(a[j]!=0) s[j]=b[j];
            else s[j]=0;
        }
        int x=tryCombination(s);
        int ib=1;
        if(x==-1 || x>i) ib=0;
        vector<int> v;
        for(int j=0;j<n;j++) if (a[j]==0) v.push_back(j);
        while(v.size()>1){
            for(int j=0;j<n;j++){
                if(a[j]!=0) s[j]=b[j];
                else s[j]=0;
            }
            vector<int> h1,h2;
            int t=v.size();
            for(int j=0;j<(t/2);j++){
                h1.push_back(v[j]);
                s[v[j]]=ib;
            }
            for(int j=(t/2);j<t;j++){
                h2.push_back(v[j]);
                s[v[j]]=(1-ib);
            }
            x=tryCombination(s);
            if(x==-1 || x>i) v=h1;
            else v=h2;
        }
        a[v.back()]=1;
        b[v.back()]=ib;
        c[v.back()]=i;
    }
    int s[n],d[n];
    for(int i=0;i<n;i++){
		s[i]=b[i];
		d[i]=c[i];
	}
    answer(s,d);
}

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