Submission #94637

#	Time	Username	Problem	Language	Result	Execution time	Memory
94637		Retro3014	동굴 (IOI13_cave)	C++17	100 / 100	960 ms	640 KiB

cave

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

using namespace std;

#define MAX_N 5000


void exploreCave(int N) {
    vector<int> a(N), b(N);
    int q[MAX_N+1];
    for(int i=0; i<N; i++){
    	for(int j=0; j<N; j++)	q[j] = 1;
    	for(int j=0; j<i; j++)	q[b[j]] = a[j];
    	int t = tryCombination(q);
    	if(t==i)	a[i] = 1;
    	else	a[i] = 0;
    	int s = 0, e = N-1, m;
    	while(s<e){
    		m = (s+e)/2;
    		for(int j=0; j<N; j++)	q[j] = 1 - a[i];
    		for(int j = s; j<=m; j++)	q[j] = a[i];
    		for(int j=0; j<i; j++)	q[b[j]] = a[j];
    		if(tryCombination(q)==i)	e = m;
    		else	s = m+1;
    	}
    	b[i] = s;
    	a[i] = 1 - a[i];
    }
   	int S[MAX_N+1], D[MAX_N+1];
    for(int i=0; i<N; i++){
    	S[b[i]] = a[i];
    	D[b[i]] = i;
    }
    answer(S, D);
}

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