Submission #500906

#	Time	Username	Problem	Language	Result	Execution time	Memory
500906		aymanrs	동굴 (IOI13_cave)	C++14	100 / 100	237 ms	580 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);//{
// 	cout << "--------------------------------\n";
// 	for(int i = 0;i < n;i++) cout << S[i] << '\n';
// 	cout << "--------------------------------\n";
// 	int r;
// 	cin >> r;
// 	return r;
// }
void answer(int S[], int D[]);//{
// 	for(int i = 0;i < n;i++) cout << S[i] << ' ' << D[i] << '\n';
// }
void exploreCave(int N){
	int S[N] = {0}, D[N];
	vector<int> s;
	for(int i = 0;i < N;i++) s.push_back(i);
	for(int i = 0;i < N;i++){
		for(int j : s) S[j] = 0;
		int l = 0, r = s.size()-1, m, b, g = tryCombination(S), f;
		if(g == -1 || g>i) f = 0;
		else {
			for(int j : s) S[j] = 1;
			f = 1;
		}
		while(l <= r){
			m = (l+r)/2;
			for(int j = l;j <= m;j++) S[s[j]] = 1^f;
			g = tryCombination(S);
			for(int j = l;j <= m;j++) S[s[j]] = f;
			if(g != -1 && g <= i){
				b = m;
				r = m-1;
			} else {
				l = m+1;
			}
		}
		D[s[b]] = i;
		S[s[b]] = f;
		s.erase(s.begin()+b);
	}
	answer(S, D);
}
// int main(){
// 	exploreCave(n);
// }

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:39:8: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |   D[s[b]] = i;
      |        ^

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