Submission #414666

#	Time	Username	Problem	Language	Result	Execution time	Memory
414666		hibye1217	Cave (IOI13_cave)	C++17	100 / 100	367 ms	452 KiB

cave

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

void exploreCave(int N) {
	int flp[5020] = {};
	int dor[5020] = {};
	bool chk[5020] = {};
	for (int i = 0; i < N; i++){
		int st = 0, ed = N-1;
		int res1 = tryCombination(flp);
		while (st < ed){
			int mid = st + ed >> 1;
			for (int j = st; j <= mid; j++){
				if (chk[j]){ continue; }
				flp[j] ^= 1;
			}
			int res2 = tryCombination(flp);
			for (int j = st; j <= mid; j++){
				if (chk[j]){ continue; }
				flp[j] ^= 1;
			}
			if ( (res1==i) ^ (res2==i) ){ ed = mid; }
			else{ st = mid+1; }
		}
		int ptr = st;
		dor[ptr] = i; chk[ptr] = 1;
		if (res1 == i){ flp[ptr] = 1; }
	}
	answer(flp, dor);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:15:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |    int mid = st + ed >> 1;
      |              ~~~^~~~

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