Submission #44717

#	Time	Username	Problem	Language	Result	Execution time	Memory
44717		Mamnoon_Siam	Cave (IOI13_cave)	C++17	100 / 100	796 ms	692 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

#define LEFT 656
#define RIGHT 564

const int maxn = 5005;

int n;
int off[maxn];
int to[maxn];
int pass[maxn];
int assigned[maxn];
vector<int> v;
int at;

int bs(int l, int r) {
	if(l == r) {
		return v[l];
	}
	int m = l + r >> 1;
	for(int i = 0; i<=m; i++) {
		pass[v[i]] = 1;
	}
	for(int i = m + 1; i <= r; i++) {
		pass[v[i]] = 0;
	}
	int side;
	if(off[at] == -1) {
		int prev = tryCombination(pass);
		int updown = prev == at;
		if(updown == 0) { // khola ace
			for(int i=l; i<=m; i++) {
				pass[v[i]] = 0;
			}
			int now = tryCombination(pass);
			if(now == at) { // bondho hoice
				side = LEFT;
				off[at] = 0;
			}
			else { // ekhono khula ace
				side = RIGHT;
				off[at] = 1;
			}
		}
		else { // bodho ace
			for(int i=l; i<=m; i++) {
				pass[v[i]] = 0;
			}
			int now = tryCombination(pass);
			if(now == at) { // ekhono bondho ace
				side = RIGHT;
				off[at] = 0;
			}
			else { // khule gece
				side = LEFT;
				off[at] = 1;
			}
		}
	}
	else {
		for(int i=l; i<=m; i++) {
			pass[v[i]] = off[at];
		}
		for(int i=m+1; i<=r; i++) {
			pass[v[i]] = off[at] ? 0 : 1;
		}
		int now = tryCombination(pass);
		if(now == at) {
			side = LEFT;
		}
		else {
			side = RIGHT;
		}
	}
	if(side == LEFT) {
		return bs(l, m);
	}
	else {
		return bs(m+1, r);
	}
}

int ans[maxn];
int sw[maxn];

void exploreCave(int N) {
    n = N;
    memset(off, -1, sizeof off);
    for(int i=0; i<n; i++) {
    	at = i;
    	v.clear();
    	for(int j=0; j<n; j++) {
    		if(assigned[j]) continue;
    		v.push_back(j);
    	}
    	for(int j=0; j<i; j++) {
    		pass[to[j]] = off[j] ? 0 : 1;
    	}
    	to[i] = bs(0, v.size()-1);
    	assigned[to[i]] = 1;
    }
    memset(pass, -1, sizeof pass);
    for(int i=0; i<n-1; i++) {
    	pass[to[i]] = off[i] ? 0 : 1;
    }
    for(int i=0; i<n; i++) {
    	if(pass[i] == -1) {
    		pass[i] = 1;
    	}
    }
    int temp = tryCombination(pass);
    if(temp == -1) {
    	off[n-1] = 0;
    }
    else {
    	off[n-1] = 1;
    }
    for(int i=0; i<n; i++) {
    	ans[to[i]] = i;
    }
    for(int i=0; i<n; i++) {
    	sw[to[i]] = off[i];
    }
    for(int i=0; i<n; i++) {
    	sw[i] = !sw[i];
    }
    answer(sw, ans);
}

Compilation message (stderr)

cave.cpp: In function 'int bs(int, int)':
cave.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~

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