Submission #1318343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318343		avahw	Lost in the cycle (IOI19_cycle)	C++20	100 / 100	1 ms	400 KiB

cycle

#include "cycle.h"
#include <bits/stdc++.h>
using namespace std;

void escape(int n) {
	// take biggest possible power of 2 that doesn't take us to other side
	if(n == 2){
		jump(1);
		return;
	}
	int p = log((n / 2)) / log(2);
	int curr = jump(1);
	int diff = curr ^ 1;
	int next_jump = pow(2, p);
	int jump_back = -1;
	while(p >= 0){
		int res = jump(next_jump);
		if(res == curr){
			next_jump = pow(2, p - 1);
			jump_back = false;
		}
		else{
			// if we went to the other side, then we need to jump back
			next_jump = (n - pow(2, p)) + pow(2, p - 1);
			jump_back = true;

		}
		p--;
	}
	// if we need to jump back, do that
	if(jump_back){
		jump(next_jump);
	}
	// if we started off in the cant zone, we need to do n / 2 + 1 jumps to get out
	if(curr == 0){
		jump(n / 2 + 1);
	}
}

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