Submission #166694

#	Time	Username	Problem	Language	Result	Execution time	Memory
166694		rianradeck	Cave (IOI13_cave)	C++17	100 / 100	315 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

using namespace std;
const int MAXN = 5010;

int s[MAXN], d[MAXN], aux[MAXN];

void exploreCave(int n){
    memset(d, -1, sizeof d);
    int x = tryCombination(s);
    if(x == -1) x = n;
    for(int p = 0;p < n;p++){
    	int bg = 0, nd = n - 1;
    	while(bg < nd){
    		int mid = (bg + nd) >> 1;
	    	for(int i = bg;i <= mid;i++)
	    		if(d[i] == -1)
	    			aux[i] = (aux[i] + 1) % 2;
    		int y = tryCombination(aux);
    		if(y == -1) y = n;
    		if((x > p && y == p) || (x == p && y > p))
    			x = y, nd = mid;
    		else
    			x = y, bg = mid + 1;
    	}
    	d[bg] = p;
    	int z = tryCombination(aux);
    	s[bg] = (z == p ? (aux[bg] + 1) % 2 : aux[bg]);
    	aux[bg] = s[bg];
    	if(z > p)
    		x = z;
    	else {
	    	x = tryCombination(aux);
	    	if(x == -1)
	    		x = n;
    	}
    }
    answer(s, d);
}

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