답안 #838687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838687	2023-08-27T15:11:40 Z	finn__	게임 (APIO22_game)	C++17	2 / 100	9 ms	14464 KB

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

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.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14416 KB	Output is correct
5	Correct	6 ms	14416 KB	Output is correct
6	Correct	6 ms	14416 KB	Output is correct
7	Correct	6 ms	14416 KB	Output is correct

Subtask #2

0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14416 KB	Output is correct
5	Correct	6 ms	14416 KB	Output is correct
6	Correct	6 ms	14416 KB	Output is correct
7	Correct	6 ms	14416 KB	Output is correct
8	Correct	7 ms	14320 KB	Output is correct
9	Correct	6 ms	14288 KB	Output is correct
10	Correct	7 ms	14344 KB	Output is correct
11	Correct	6 ms	14316 KB	Output is correct
12	Correct	9 ms	14464 KB	Output is correct
13	Incorrect	7 ms	14416 KB	Wrong Answer[1]
14	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14416 KB	Output is correct
5	Correct	6 ms	14416 KB	Output is correct
6	Correct	6 ms	14416 KB	Output is correct
7	Correct	6 ms	14416 KB	Output is correct
8	Correct	7 ms	14320 KB	Output is correct
9	Correct	6 ms	14288 KB	Output is correct
10	Correct	7 ms	14344 KB	Output is correct
11	Correct	6 ms	14316 KB	Output is correct
12	Correct	9 ms	14464 KB	Output is correct
13	Incorrect	7 ms	14416 KB	Wrong Answer[1]
14	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14416 KB	Output is correct
5	Correct	6 ms	14416 KB	Output is correct
6	Correct	6 ms	14416 KB	Output is correct
7	Correct	6 ms	14416 KB	Output is correct
8	Correct	7 ms	14320 KB	Output is correct
9	Correct	6 ms	14288 KB	Output is correct
10	Correct	7 ms	14344 KB	Output is correct
11	Correct	6 ms	14316 KB	Output is correct
12	Correct	9 ms	14464 KB	Output is correct
13	Incorrect	7 ms	14416 KB	Wrong Answer[1]
14	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14416 KB	Output is correct
5	Correct	6 ms	14416 KB	Output is correct
6	Correct	6 ms	14416 KB	Output is correct
7	Correct	6 ms	14416 KB	Output is correct
8	Correct	7 ms	14320 KB	Output is correct
9	Correct	6 ms	14288 KB	Output is correct
10	Correct	7 ms	14344 KB	Output is correct
11	Correct	6 ms	14316 KB	Output is correct
12	Correct	9 ms	14464 KB	Output is correct
13	Incorrect	7 ms	14416 KB	Wrong Answer[1]
14	Halted	0 ms	0 KB	-