# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
226528 | jiahng | Lost in the cycle (IOI19_cycle) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include "cycle.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
int cur = 0;
int N;
unordered_map <int,bool> memo,vis;
bool qry(int a, bool jumping){
//set cur to a
if (vis[a] && !jumping){
//cout<<a<<' ';
return memo[a];
}
bool res = jump((a - cur + 2*N) % N);
cur = a;
vis[a] = 1;
memo[a] = res;
return res;
}
void check(int x){
if (!qry(x+1,0)){
qry(x, 1);
}else{
qry(x + N/2, 1);
}
}
void escape(int n) {
N = n;
memo.clear();
vis.clear();
if (N == 2){
jump(1);
return;
}
int l = 0; int r = N - 1;
bool f = qry(0,0);
while (l+1 < r){
//cout<<l<<' '<<r<<'\n';
int mid = (l+r)/2;
if (qry(mid,0) == f){
l = mid;
continue;
if (mid >= N/2) r = mid;
else l = mid;
}else{
r = mid;
//f = !f;
}
}
//cout<<l<<' ';
if (!qry(l,0)){
if (qry(l+1,0)) l++;
else l--;
}
//cout<<l<<' ';
check(l);
}