Submission #1072032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072032		NeroZein	How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid)	C++17	25 / 100	2 ms	600 KiB

avoid

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

using namespace std; 

const int LOG = 10;

pair<int, int> scout(int R, int H) {
	int n = 1000;
	if (H == 1) {
		for (int j = 0; j < LOG; ++j) {
			vector<int> vec; 
			for (int i = 1; i <= n; ++i) {
			  if (i >> j & 1) {
				  vec.push_back(i); 
			  }
			}
			send(vec);
		}
		vector<int> res = wait();
		int a = 0, b = 0;
		for (int j = 0; j < LOG; ++j) {
			if (res[j]) {
				a += 1 << j;
				b += 1 << j; 
			}
		}
		return {a, b};
	} else if (H == 20) {
		int l = 1, r = n;
		while (l < r) {
			int mid = (l + r) >> 1;
			vector<int> vec; 
			for (int i = 1; i <= mid; ++i) {
				vec.push_back(i);
			}
			send(vec);
			vector<int> res = wait();
			if (res[0] == 1) {
				r = mid;
			} else {
				l = mid + 1; 
			}
		}
		int a = l;
		l = 1, r = n;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			vector<int> vec;
			for (int i = n; i >= mid; --i) {
				vec.push_back(i);
			}
			send(vec);
			vector<int> res = wait();
			if (res[0] == 1) {
				l = mid;
			} else {
				r = mid - 1; 
			}
		}
		int b = l;
		return {a, b}; 
	}
	for (int j = 0; j < LOG; ++j) {
		vector<int> vec[2]; 
		for (int i = 1; i <= n; ++i) {
			vec[i >> j & 1].push_back(i);
		}
		send(vec[0]);
		send(vec[1]);
	}
	vector<int> res = wait();
	assert((int) res.size() == 2 * LOG);
	vector<int> same(LOG, -1);
	int a = 0, b = 0; 
	for (int j = 0, cur = 0; j < LOG; ++j, cur += 2) {
		if (res[cur] == 1 && res[cur + 1] == 0) {
			same[j] = 0; 
		} else if (res[cur] == 0 && res[cur + 1] == 1) {
			same[j] = 1; 
			a += (1 << j);
			b += (1 << j); 
		}
	}
	int msb = -1;
	for (int j = LOG - 1; j >= 0; --j) {
		if (same[j] == -1) {
			msb = j; 
			break; 
		}
	}
	if (msb == -1) {
		return {a, b}; 
	}
	b += (1 << msb);
	for (int j = 0; j < msb; ++j) {
		vector<int> vec[2]; 
		for (int i = 1; i <= n; ++i) {
			if (i >> msb & 1) {
				vec[i >> j & 1].push_back(i);
			}
		}
		send(vec[1]);
	}
	res = wait();
	for (int j = 0; j < msb; ++j) {
		if (same[j] != -1) {
			continue; 
		}
		if (res[j] == 1) {
			b += (1 << j);
		} else {
			a += (1 << j);
		}
	}
	return {a, b}; 
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75