Submission #1105479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105479		lkateris	Cave (IOI13_cave)	C++17	100 / 100	182 ms	848 KiB

cave

#include "cave.h"
#include <iostream>
#include <vector>

using namespace std;

bool vis[5005];
vector<int> switches;
int corr;

void exploreCave(int N) {
    int S[N],D[N];
    
    for(int i=0;i<N;++i) {
            switches.clear();
            for(int j=0;j<N;++j) if (!vis[j]) switches.push_back(j);
            for(int j=0;j<N-i;++j) S[switches[j]] = 0;
            if (tryCombination(S) == i) corr = 1;
            else corr = 0;
            for(int j=0;j<N-i;++j) S[switches[j]] = corr^1;
                    
            int l = 0;
            int r = N-i-1;

            while (l < r) {
                  int mid = (l+r)/2;
                  for (int j=l; j <= mid; ++j) S[switches[j]] = corr;
                  int f = tryCombination(S);
                  for (int j=l; j <= mid; ++j) S[switches[j]] = corr^1;

                  if (f == i) l = mid+1;
                  else r = mid;
                  }
            vis[switches[l]] = true;
            S[switches[l]] = corr;    
            D[switches[l]] = i;  
                  
    }
    answer(S,D);
}

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