답안 #640418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640418	2022-09-14T15:20:08 Z	qwerasdfzxcl	게임 (APIO22_game)	C++17	100 / 100	1888 ms	96716 KB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> adj[600600], INV[600600];
int n, k, cyc;
ll a[600600]; ///1 -> left, 2 -> right, 3 -> cycle (bit string)

void add_edge(int x, int y, int first = 1){
    if (first) {adj[x].push_back(y); INV[y].push_back(x);}
    if (cyc) return;

    int l = 1, r = k;
    ll prvx = a[x], prvy = a[y];

    for (int i=0;;i+=2){
        if (l>r) break;
        int m = (l+r)>>1;
        a[x] |= (ll)((x==m)?1:((x==m+n)?2:0))<<i;
        a[y] |= (ll)((y==m)?1:((y==m+n)?2:0))<<i;

        ll X = (a[x]&(3LL<<i))>>i, Y = (a[y]&(3LL<<i))>>i;
        Y |= X&2;
        X |= Y&1;

        if (X==3 || Y==3) {cyc = 1; break;}
        if (X!=Y) break;

        a[x] |= X<<i, a[y] |= Y<<i;
        if (X&1) r = m-1;
        else if (X&2) l = m+1;
        else break;
    }

    if (prvx!=a[x]) for (auto &nx:INV[x]) add_edge(nx, x, 0);
    if (prvy!=a[y]) for (auto &ny:adj[y]) add_edge(y, ny, 0);
}

void init(int N, int K) {
    n = N, k = K;

    for (int i=1;i<k;i++){
        add_edge(i, i+n);
        add_edge(i+n, i+1);
    }
    add_edge(k, k+n);
}

int add_teleporter(int u, int v) {
    ++u, ++v;
    add_edge(u<=k?u+n:u, v);
    return cyc;
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	28496 KB	Output is correct
2	Correct	17 ms	28460 KB	Output is correct
3	Correct	14 ms	28540 KB	Output is correct
4	Correct	14 ms	28496 KB	Output is correct
5	Correct	14 ms	28432 KB	Output is correct
6	Correct	15 ms	28496 KB	Output is correct
7	Correct	16 ms	28496 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	28496 KB	Output is correct
2	Correct	17 ms	28460 KB	Output is correct
3	Correct	14 ms	28540 KB	Output is correct
4	Correct	14 ms	28496 KB	Output is correct
5	Correct	14 ms	28432 KB	Output is correct
6	Correct	15 ms	28496 KB	Output is correct
7	Correct	16 ms	28496 KB	Output is correct
8	Correct	13 ms	28496 KB	Output is correct
9	Correct	14 ms	28496 KB	Output is correct
10	Correct	14 ms	28468 KB	Output is correct
11	Correct	16 ms	28412 KB	Output is correct
12	Correct	18 ms	28476 KB	Output is correct
13	Correct	15 ms	28496 KB	Output is correct
14	Correct	18 ms	28496 KB	Output is correct
15	Correct	13 ms	28476 KB	Output is correct
16	Correct	15 ms	28516 KB	Output is correct
17	Correct	14 ms	28524 KB	Output is correct
18	Correct	14 ms	28520 KB	Output is correct
19	Correct	15 ms	28524 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	28496 KB	Output is correct
2	Correct	17 ms	28460 KB	Output is correct
3	Correct	14 ms	28540 KB	Output is correct
4	Correct	14 ms	28496 KB	Output is correct
5	Correct	14 ms	28432 KB	Output is correct
6	Correct	15 ms	28496 KB	Output is correct
7	Correct	16 ms	28496 KB	Output is correct
8	Correct	13 ms	28496 KB	Output is correct
9	Correct	14 ms	28496 KB	Output is correct
10	Correct	14 ms	28468 KB	Output is correct
11	Correct	16 ms	28412 KB	Output is correct
12	Correct	18 ms	28476 KB	Output is correct
13	Correct	15 ms	28496 KB	Output is correct
14	Correct	18 ms	28496 KB	Output is correct
15	Correct	13 ms	28476 KB	Output is correct
16	Correct	15 ms	28516 KB	Output is correct
17	Correct	14 ms	28524 KB	Output is correct
18	Correct	14 ms	28520 KB	Output is correct
19	Correct	15 ms	28524 KB	Output is correct
20	Correct	16 ms	28496 KB	Output is correct
21	Correct	18 ms	28528 KB	Output is correct
22	Correct	17 ms	28496 KB	Output is correct
23	Correct	16 ms	28532 KB	Output is correct
24	Correct	17 ms	28592 KB	Output is correct
25	Correct	17 ms	28712 KB	Output is correct
26	Correct	19 ms	28612 KB	Output is correct
27	Correct	18 ms	28660 KB	Output is correct
28	Correct	17 ms	28752 KB	Output is correct
29	Correct	17 ms	28764 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	28496 KB	Output is correct
2	Correct	17 ms	28460 KB	Output is correct
3	Correct	14 ms	28540 KB	Output is correct
4	Correct	14 ms	28496 KB	Output is correct
5	Correct	14 ms	28432 KB	Output is correct
6	Correct	15 ms	28496 KB	Output is correct
7	Correct	16 ms	28496 KB	Output is correct
8	Correct	13 ms	28496 KB	Output is correct
9	Correct	14 ms	28496 KB	Output is correct
10	Correct	14 ms	28468 KB	Output is correct
11	Correct	16 ms	28412 KB	Output is correct
12	Correct	18 ms	28476 KB	Output is correct
13	Correct	15 ms	28496 KB	Output is correct
14	Correct	18 ms	28496 KB	Output is correct
15	Correct	13 ms	28476 KB	Output is correct
16	Correct	15 ms	28516 KB	Output is correct
17	Correct	14 ms	28524 KB	Output is correct
18	Correct	14 ms	28520 KB	Output is correct
19	Correct	15 ms	28524 KB	Output is correct
20	Correct	16 ms	28496 KB	Output is correct
21	Correct	18 ms	28528 KB	Output is correct
22	Correct	17 ms	28496 KB	Output is correct
23	Correct	16 ms	28532 KB	Output is correct
24	Correct	17 ms	28592 KB	Output is correct
25	Correct	17 ms	28712 KB	Output is correct
26	Correct	19 ms	28612 KB	Output is correct
27	Correct	18 ms	28660 KB	Output is correct
28	Correct	17 ms	28752 KB	Output is correct
29	Correct	17 ms	28764 KB	Output is correct
30	Correct	29 ms	29872 KB	Output is correct
31	Correct	27 ms	29380 KB	Output is correct
32	Correct	50 ms	32088 KB	Output is correct
33	Correct	35 ms	30536 KB	Output is correct
34	Correct	84 ms	36080 KB	Output is correct
35	Correct	59 ms	32544 KB	Output is correct
36	Correct	72 ms	30592 KB	Output is correct
37	Correct	62 ms	30792 KB	Output is correct
38	Correct	57 ms	30608 KB	Output is correct
39	Correct	46 ms	30608 KB	Output is correct
40	Correct	66 ms	35748 KB	Output is correct
41	Correct	57 ms	33360 KB	Output is correct
42	Correct	46 ms	31304 KB	Output is correct
43	Correct	102 ms	32168 KB	Output is correct
44	Correct	89 ms	32748 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	28496 KB	Output is correct
2	Correct	17 ms	28460 KB	Output is correct
3	Correct	14 ms	28540 KB	Output is correct
4	Correct	14 ms	28496 KB	Output is correct
5	Correct	14 ms	28432 KB	Output is correct
6	Correct	15 ms	28496 KB	Output is correct
7	Correct	16 ms	28496 KB	Output is correct
8	Correct	13 ms	28496 KB	Output is correct
9	Correct	14 ms	28496 KB	Output is correct
10	Correct	14 ms	28468 KB	Output is correct
11	Correct	16 ms	28412 KB	Output is correct
12	Correct	18 ms	28476 KB	Output is correct
13	Correct	15 ms	28496 KB	Output is correct
14	Correct	18 ms	28496 KB	Output is correct
15	Correct	13 ms	28476 KB	Output is correct
16	Correct	15 ms	28516 KB	Output is correct
17	Correct	14 ms	28524 KB	Output is correct
18	Correct	14 ms	28520 KB	Output is correct
19	Correct	15 ms	28524 KB	Output is correct
20	Correct	16 ms	28496 KB	Output is correct
21	Correct	18 ms	28528 KB	Output is correct
22	Correct	17 ms	28496 KB	Output is correct
23	Correct	16 ms	28532 KB	Output is correct
24	Correct	17 ms	28592 KB	Output is correct
25	Correct	17 ms	28712 KB	Output is correct
26	Correct	19 ms	28612 KB	Output is correct
27	Correct	18 ms	28660 KB	Output is correct
28	Correct	17 ms	28752 KB	Output is correct
29	Correct	17 ms	28764 KB	Output is correct
30	Correct	29 ms	29872 KB	Output is correct
31	Correct	27 ms	29380 KB	Output is correct
32	Correct	50 ms	32088 KB	Output is correct
33	Correct	35 ms	30536 KB	Output is correct
34	Correct	84 ms	36080 KB	Output is correct
35	Correct	59 ms	32544 KB	Output is correct
36	Correct	72 ms	30592 KB	Output is correct
37	Correct	62 ms	30792 KB	Output is correct
38	Correct	57 ms	30608 KB	Output is correct
39	Correct	46 ms	30608 KB	Output is correct
40	Correct	66 ms	35748 KB	Output is correct
41	Correct	57 ms	33360 KB	Output is correct
42	Correct	46 ms	31304 KB	Output is correct
43	Correct	102 ms	32168 KB	Output is correct
44	Correct	89 ms	32748 KB	Output is correct
45	Correct	258 ms	42196 KB	Output is correct
46	Correct	26 ms	31540 KB	Output is correct
47	Correct	33 ms	31696 KB	Output is correct
48	Correct	351 ms	61676 KB	Output is correct
49	Correct	315 ms	49712 KB	Output is correct
50	Correct	1393 ms	89204 KB	Output is correct
51	Correct	1286 ms	69780 KB	Output is correct
52	Correct	695 ms	49684 KB	Output is correct
53	Correct	895 ms	50008 KB	Output is correct
54	Correct	982 ms	52160 KB	Output is correct
55	Correct	1228 ms	50644 KB	Output is correct
56	Correct	1684 ms	52084 KB	Output is correct
57	Correct	1010 ms	87636 KB	Output is correct
58	Correct	971 ms	87820 KB	Output is correct
59	Correct	1056 ms	87652 KB	Output is correct
60	Correct	1153 ms	88080 KB	Output is correct
61	Correct	1226 ms	87688 KB	Output is correct
62	Correct	883 ms	66124 KB	Output is correct
63	Correct	717 ms	62920 KB	Output is correct
64	Correct	1699 ms	96716 KB	Output is correct
65	Correct	701 ms	56060 KB	Output is correct
66	Correct	660 ms	52128 KB	Output is correct
67	Correct	1115 ms	62680 KB	Output is correct
68	Correct	344 ms	56124 KB	Output is correct
69	Correct	185 ms	50480 KB	Output is correct
70	Correct	1260 ms	75848 KB	Output is correct
71	Correct	507 ms	56728 KB	Output is correct
72	Correct	410 ms	53160 KB	Output is correct
73	Correct	1087 ms	69400 KB	Output is correct
74	Correct	1879 ms	54916 KB	Output is correct
75	Correct	1700 ms	65596 KB	Output is correct
76	Correct	1888 ms	73316 KB	Output is correct

답안 #640418

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 10.0 / 10.0

Subtask #3 18.0 / 18.0

Subtask #4 30.0 / 30.0

Subtask #5 40.0 / 40.0

Subtask #1
2.0 / 2.0

Subtask #2
10.0 / 10.0

Subtask #3
18.0 / 18.0

Subtask #4
30.0 / 30.0

Subtask #5
40.0 / 40.0