Submission #1193838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193838		chaeryeong	Lost in the cycle (IOI19_cycle)	C++20	33 / 100	0 ms	412 KiB

cycle

#include "cycle.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
	return uniform_int_distribution <int> (l, r) (rng);
}
int sum, n;
int ask (int x) {
	sum += x; sum %= n;
	return jump(x);
}
void escape (int _N) {
	n = _N;
	assert(n != 2);
	sum = 0;
	if (ask(0)) {
		//p >= ceil(n / 2)
		//p + x < ceil(n / 2)
		while (ask(random(n / 2, n - 1)));
		int x = sum;
		int l = 0, r = x, ans;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (!ask((mid - sum + n) % n)) {
				r = mid - 1; ans = mid;
			} else {
				l = mid + 1;
			}
		}
		ask((ans - sum + n - 1) % n);
	} else {
		//p < ceil(n / 2)
		//p + x >= ceil(n / 2)
		while (!ask(random(n / 2, n - 1)));
		int x = sum;
		int l = 0, r = x, ans;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (ask((mid - sum + n) % n)) {
				r = mid - 1; ans = mid;
			} else {
				l = mid + 1;
			}
		}
		ask((ans - sum + (n / 2) + n) % n);
	}
}

• Subtask 1: 0 / 11
• Subtask 2: 33 / 33
• Subtask 3: 0 / 56