| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1357730 | Skymagic | 게임 (APIO22_game) | C++17 | 0 ms | 0 KiB |
/*******************
* what the sigma *
********************/
#include <iostream>
#include <vector>
#include <map>
#include <chrono>
#include <set>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define tll tuple<ll,ll,ll>
#define sz(x) ((int)x.size())
#define pb push_back
const ll mod = 1e9+7,maxn=300005;
const ll INF=(ll)9e18;
int n,k;
int l[maxn],r[maxn]; // l=max planet to go out r=min planet to go in
ve<int> in[maxn],out[maxn];
void init(int N, int K){
n=N,k=K;
for (int i=1;i<=k;i++) {
r[i]=l[i]=i;
}
for (int i=k+1;i<=n;i++) {
r[i]=k+1;
l[i]=0;
}
}
bool chk(int u);
bool upd(int u,int v) {
if (r[v]<=l[u]) return 1;
int mid1=(l[u]+r[u])>>1,mid2=(l[v]+r[v])>>1;
if (r[v]<=mid1) {
r[u]=mid1;
return chk(u);
}
if (mid2+1<=l[u]) {
l[u]=mid2+1;
return chk(v);
}
return 0;
}
bool chk(int u) {
bool h=0;
for (auto&i:in[u]) h|=upd(i,u);
for (auto&i:out[u]) h|=upd(u,i);
return h;
}