Submission #838687

#	Time	Username	Problem	Language	Result	Execution time	Memory
838687		finn__	Game (APIO22_game)	C++17	2 / 100	9 ms	14464 KiB

game

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

constexpr size_t N = 300000;

size_t n, k, l[N], r[N];
vector<size_t> in[N], out[N];

bool update(size_t u, bool direction)
{
    if (!direction)
    {
        r[u] = (l[u] + r[u]) / 2;
        if (l[u] >= r[u])
            return 1;
        for (auto const &v : in[u])
            if (r[u] <= (l[v] + r[v]) / 2 && update(v, 0))
                return 1;
    }
    else
    {
        l[u] = (l[u] + r[u]) / 2 + 1;
        if (l[u] >= r[u])
            return 1;
        for (auto const &v : out[u])
            if (l[u] >= (l[v] + r[v]) / 2 + 1 && update(v, 1))
                return 1;
    }
    return 0;
}

void init(int n_, int k_)
{
    n = n_, k = k_;
    for (size_t i = 0; i < k; ++i)
        l[i] = i + 1, r[i] = i + 2;
    for (size_t i = k; i < n; ++i)
        l[i] = 0, r[i] = k + 1;
}

int add_teleporter(int u, int v)
{
    if (u == v && u < k)
        return 1;
    if (l[u] >= (l[v] + r[v]) / 2 + 1)
        if (update(v, 1))
            return 1;
    if (r[v] <= (l[u] + r[u]) / 2)
        if (update(u, 0))
            return 1;
    out[u].push_back(v);
    in[v].push_back(u);
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if (u == v && u < k)
      |                   ~~^~~

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