Submission #1201924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201924		adiyer	Game (APIO22_game)	C++20	100 / 100	658 ms	117028 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 11;

int n, k, ok;
int was[MAXN], r[MAXN], l[MAXN];

vector < int > g[MAXN], rg[MAXN];

void init(int _n, int _k) {
    n = _n + 1, k = _k + 1;
    for(int i = 0; i < k; i++) l[i] = i, r[i] = i + 1;
    for(int i = k; i < n; i++) l[i] = 0, r[i] = k;
}

bool c(int a);

bool f(int a, int b){
    if(r[a] <= l[b]) return 0;
    if(l[a] >= r[b]) return 1;
    if(l[a] == l[b] && r[a] == r[b]) return 0;
    if((l[a] + r[a]) / 2 >= r[b]){
        r[a] = (l[a] + r[a]) / 2;
        return c(a);
    }
    else if(l[a] >= (l[b] + r[b]) / 2){
        l[b] = (l[b] + r[b]) / 2;
        return c(b);
    }
    return 0;
}

bool c(int a){
    for(int b : rg[a])
        if(f(b, a))
            return 1;
    for(int b : g[a]){
        if(f(a, b))
            return 1;
    }
    return 0;
}

int add_teleporter(int u, int v){
    u++, v++; 
    if(v < k) v--;
    g[u].push_back(v), rg[v].push_back(u); 
    if(f(u, v)) return 1;
    else return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40