Submission #393146

#	Time	Username	Problem	Language	Result	Execution time	Memory
393146		JimmyZJX	Cup of Jamshid (IOI17_cup)	C++14	100 / 100	2 ms	332 KiB

cup

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

int ask_shahrasb(int x, int y);

#define bit1(x, a) (((x) & (1 << (a))) > 0)

Vi find_cup() {
	int x0 = -(1 << 29), y0 = -(1 << 29);
	int xl = 30, yl = 30;
	// [x0, x0 + 2^xl)
	while (xl + yl > 0) {

		if (xl == yl && xl < 30) {
			xl--; yl--;
			int xq = x0 - (1 << xl);
			int r = ask_shahrasb(xq, y0);
			int r_2 = r >> xl;
			assert(r_2 < 4);

			int len = 1 << xl;
			switch (r_2) {
			case 0b11: x0 += len; y0 += len; break;
			case 0b10: x0 += len; break;
			case 0b01: break;
			case 0b00: y0 += len; break;
			}
		} else if (yl > xl) {
			// dec yl
			int r = ask_shahrasb(x0, y0);
			yl--;
			if (bit1(r, yl)) {
				y0 += 1 << yl;
			}
		} else {
			// dec xl
			xl--;
			int r = ask_shahrasb(x0, y0 + (1 << xl));
			if (bit1(r, xl)) {
				x0 += 1 << xl;
			}
		}
	}
	return Vi{ x0, y0 };
}

#ifdef TEST_LOCAL
int cnt = 0;
int ax = -123897, ay = 378732719;
int ask_shahrasb(int x, int y) {
	cnt++;
	assert(abs(x) <= (int)1e9 && abs(y) <= (int)1e9);
	return abs(x - ax) ^ abs(y - ay);
}

int main() {
	auto r = find_cup();
	assert(r[0] == ax && r[1] == ay);

	return 0;
}
#endif

• Subtask 1: 100 / 100