QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#606386#9161. Naval battleBucketsmith46 39ms12108kbC++203.8kb2024-10-03 02:46:152024-10-03 02:46:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-03 02:46:16]
  • 评测
  • 测评结果:46
  • 用时:39ms
  • 内存:12108kb
  • [2024-10-03 02:46:15]
  • 提交

answer

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

using pic = pair<int, char>;
using pii = pair<int, int>;
using node = tuple<int, int, int>;
const int N = 2e5 + 10;

int n, x[N], y[N];
char d[N];

bool crash[N];

int collide(int i, int j) {
    if(d[i] == d[j]) return -1;
    if(x[i] == x[j]) {
        if(y[i] < y[j] && d[i] == 'S' && d[j] == 'N') return (y[j] - y[i]) / 2;
        if(y[i] > y[j] && d[j] == 'S' && d[i] == 'N') return (y[i] - y[j]) / 2;
        return -1;
    }else if(y[i] == y[j]) {
        if(x[i] < x[j] && d[i] == 'E' && d[j] == 'W') return (x[j] - x[i]) / 2;
        if(x[j] < x[i] && d[j] == 'E' && d[i] == 'W') return (x[i] - x[j]) / 2;
        return -1;
    }else if(x[i] + y[i] == x[j] + y[j]) {
        if(x[i] > x[j] && d[i] == 'S' && d[j] == 'E') return x[i] - x[j];
        if(x[i] > x[j] && d[i] == 'W' && d[j] == 'N') return x[i] - x[j];
        if(x[j] > x[i] && d[j] == 'S' && d[i] == 'E') return x[j] - x[i];
        if(x[j] > x[i] && d[j] == 'W' && d[i] == 'N') return x[j] - x[i];
        return -1;
    }else if(x[i] - y[i] == x[j] - y[j]) {
        if(x[i] > x[j] && d[i] == 'N' && d[j] == 'E') return x[i] - x[j];
        if(x[i] > x[j] && d[i] == 'W' && d[j] == 'S') return x[i] - x[j];
        if(x[j] > x[i] && d[j] == 'N' && d[i] == 'E') return x[j] - x[i];
        if(x[j] > x[i] && d[j] == 'W' && d[i] == 'S') return x[j] - x[i];
        return -1;
    }
    return -1;
}

map<pic, set<pii> > mp[4];

priority_queue<node, vector<node>, greater<node> > pq;

void findCollide(int i) {
    if(crash[i]) return;
    int t = INT_MAX, tar = -1;
    for(char c : "NSWE"s) {
        if(c == d[i]) continue;
        for(auto [op, tx, ty] : vector<node>{node{0, x[i], y[i]}, node{1, y[i], x[i]}, node{2, x[i] + y[i], x[i]}, node{3, x[i] - y[i], x[i]}}) {
            auto &s = mp[op][pic{tx, c}];
            auto it = s.lower_bound(pii{ty, N});
            if(it != s.end()) {
                int x = collide(i, it->second);
                if(x != -1 && x < t) {
                    t = x;
                    tar = it->second;
                }
            }
            if(it != s.begin()) {
                it --;
                int x = collide(i, it->second);
                if(x != -1 && x < t) {
                    t = x;
                    tar = it->second;
                }
            }
        }
    }
    if(t < INT_MAX) pq.emplace(t, i, tar);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> x[i] >> y[i] >> d[i];
        mp[0][pic{x[i], d[i]}].insert({y[i], i});
        mp[1][pic{y[i], d[i]}].insert({x[i], i});
        mp[2][pic{x[i] + y[i], d[i]}].insert({x[i], i});
        mp[3][pic{x[i] - y[i], d[i]}].insert({x[i], i});
    }

    for(int i = 1; i <= n; i ++)
        findCollide(i);
    
    while(pq.size()) {
        auto [t, u, v] = pq.top();
        pq.pop();
        if(crash[u] || crash[v]) {
            findCollide(u);
            findCollide(v);
            continue;
        }
        vector<int> w{u, v};
        while(pq.size() && get<0>(pq.top()) == t) {
            auto [it, iu, iv] = pq.top();
            pq.pop();

            if(crash[iu] || crash[iv]) {
                findCollide(iu);
                findCollide(iv);
                continue;
            }
            w.emplace_back(iu);
            w.emplace_back(iv);
        }

        for(int i : w) {
            crash[i] = true;
            mp[0][pic{x[i], d[i]}].erase({y[i], i});
            mp[1][pic{y[i], d[i]}].erase({x[i], i});
            mp[2][pic{x[i] + y[i], d[i]}].erase({x[i], i});
            mp[3][pic{x[i] - y[i], d[i]}].erase({x[i], i});
        }
    }

    for(int i = 1; i <= n; i ++)
        if(!crash[i]) cout << i << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 0ms
memory: 3640kb

input:

2
675333810 792019962 W
851860476 960355168 W

output:

1
2

result:

ok 

Test #2:

score: 6
Accepted
time: 0ms
memory: 3812kb

input:

2
714148610 688520844 W
359519570 789553998 S

output:

1
2

result:

ok 

Test #3:

score: 6
Accepted
time: 0ms
memory: 3576kb

input:

2
743286406 87591094 E
108453484 326740470 S

output:

1
2

result:

ok 

Test #4:

score: 6
Accepted
time: 0ms
memory: 3636kb

input:

2
629499666 659260200 W
391550936 897208930 N

output:


result:

ok 

Test #5:

score: 6
Accepted
time: 0ms
memory: 3792kb

input:

2
509095668 374922996 W
325521434 191348762 S

output:


result:

ok 

Test #6:

score: 6
Accepted
time: 0ms
memory: 3836kb

input:

2
357656592 713571312 E
456601638 614626266 S

output:


result:

ok 

Test #7:

score: 6
Accepted
time: 0ms
memory: 3556kb

input:

2
353512742 374956722 W
265604916 462864548 N

output:


result:

ok 

Test #8:

score: 6
Accepted
time: 0ms
memory: 3572kb

input:

2
253519292 302668732 E
436627396 119560628 S

output:


result:

ok 

Test #9:

score: 6
Accepted
time: 0ms
memory: 3624kb

input:

2
741954822 709863076 W
516385128 484293380 S

output:

1
2

result:

ok 

Test #10:

score: 6
Accepted
time: 0ms
memory: 3620kb

input:

2
268851874 524109226 E
503673708 758931058 N

output:

1
2

result:

ok 

Test #11:

score: 6
Accepted
time: 0ms
memory: 3852kb

input:

2
629380956 395789270 S
557401140 467769088 E

output:

1
2

result:

ok 

Test #12:

score: 6
Accepted
time: 0ms
memory: 3556kb

input:

2
606361496 587557658 N
667076156 526843000 W

output:

1
2

result:

ok 

Test #13:

score: 6
Accepted
time: 0ms
memory: 3516kb

input:

2
270428340 629167054 N
270428342 179345630 S

output:

1
2

result:

ok 

Subtask #2:

score: 12
Accepted

Test #14:

score: 12
Accepted
time: 1ms
memory: 3932kb

input:

100
32 46 N
8 24 W
74 86 W
2 76 N
90 70 N
34 74 N
4 68 N
42 26 N
66 94 N
28 40 W
96 12 W
82 78 W
54 24 N
36 42 W
92 68 W
0 26 N
14 54 N
94 66 N
26 52 N
66 12 W
72 6 W
64 96 W
6 20 N
4 22 W
26 42 N
40 28 W
70 76 N
18 60 N
62 16 N
30 48 N
36 36 W
42 36 W
52 94 N
62 98 N
0 78 N
70 2 W
28 50 N
80 80 W
8...

output:


result:

ok 

Test #15:

score: 12
Accepted
time: 1ms
memory: 3624kb

input:

100
70 62 N
56 42 N
42 56 W
64 4 N
50 48 W
56 76 N
78 20 W
96 96 W
60 72 N
44 24 N
2 10 N
52 80 W
38 30 N
94 4 W
58 74 W
68 30 W
54 76 N
0 68 N
36 32 N
10 58 W
70 60 W
86 92 N
100 78 W
2 66 W
20 48 N
16 52 N
8 60 N
98 94 N
86 46 W
74 24 W
26 42 W
66 66 W
28 40 W
56 12 W
90 42 W
8 4 W
76 30 W
78 54 W...

output:


result:

ok 

Test #16:

score: 12
Accepted
time: 1ms
memory: 3608kb

input:

100
36 44 E
96 66 E
28 20 E
36 2 E
32 64 W
76 58 E
82 20 E
76 50 E
22 48 W
38 52 E
90 16 N
22 12 W
64 82 S
84 14 E
92 52 E
76 36 E
72 52 N
100 58 S
82 4 E
2 0 N
90 100 E
68 8 S
24 36 S
80 86 W
72 56 W
8 66 W
84 18 S
18 60 N
64 96 E
2 76 S
74 90 E
64 0 S
12 10 S
56 40 S
40 6 S
2 4 S
74 2 S
90 80 N
2 ...

output:

1
2
3
4
5
6
8
10
11
12
13
14
15
19
20
21
23
24
26
28
29
30
31
32
33
35
36
37
39
40
41
42
45
46
47
48
49
50
51
53
54
56
57
58
59
61
62
63
64
65
69
70
71
73
74
76
77
78
79
81
83
84
85
87
89
91
92
93
95
96
98
99

result:

ok 

Test #17:

score: 12
Accepted
time: 1ms
memory: 3716kb

input:

100
24 52 S
72 60 E
72 64 W
98 52 N
46 30 E
18 62 W
70 6 S
14 58 S
12 24 W
2 54 E
20 58 S
70 40 S
8 90 E
92 16 S
26 42 E
72 8 N
46 48 S
18 64 N
80 78 E
46 20 S
26 76 W
56 68 N
82 2 N
78 72 N
54 6 N
98 8 S
52 64 N
64 88 W
6 90 N
58 96 S
30 4 E
54 48 N
36 10 S
4 32 S
20 40 W
70 30 W
16 16 W
84 80 N
52...

output:

1
2
9
11
13
14
15
16
17
19
21
22
23
24
25
26
28
29
30
32
35
37
38
39
40
44
45
46
47
48
49
51
55
57
58
59
61
62
63
64
65
66
67
68
71
72
74
76
79
80
81
84
86
87
88
90
92
93
95
96
99
100

result:

ok 

Test #18:

score: 12
Accepted
time: 1ms
memory: 3900kb

input:

100
58 98 W
90 40 W
62 34 W
56 72 S
96 56 E
62 62 E
54 32 S
84 98 W
62 100 N
18 82 W
36 86 N
34 64 W
94 74 N
90 78 N
14 42 S
58 78 W
6 60 N
60 92 W
64 60 N
84 58 S
0 84 N
36 80 W
12 0 N
28 54 E
24 64 N
60 16 E
26 40 S
32 30 W
26 28 S
94 78 N
26 0 E
20 84 E
0 56 S
8 48 N
76 0 S
6 94 N
6 14 W
80 22 S
...

output:

1
3
4
5
9
11
12
13
14
15
18
19
20
22
23
24
25
28
29
30
32
34
37
38
41
43
47
49
50
53
55
56
58
59
60
62
63
65
66
68
69
72
73
74
75
76
77
78
79
80
81
82
86
88
89
91
92
93
94
96
97
98
99
100

result:

ok 

Test #19:

score: 12
Accepted
time: 1ms
memory: 3604kb

input:

100
4 18 N
2 2 W
0 2 E
4 2 E
8 14 N
6 14 N
6 2 W
2 14 W
0 24 E
0 22 E
0 18 N
0 20 E
4 32 W
8 6 E
2 12 N
8 20 S
2 22 N
4 38 S
8 18 N
4 24 W
8 12 W
2 32 N
8 4 N
4 14 N
2 28 W
8 22 S
0 32 W
8 28 N
8 0 E
8 24 W
8 30 W
0 12 W
4 10 E
0 28 S
2 10 E
8 8 S
6 36 S
2 24 W
0 6 N
4 22 W
2 8 N
2 16 S
4 34 N
6 28 ...

output:

11
14
18
20
22
23
25
27
29
31
32
33
36
37
39
44
45
53
57
59
61
62
63
66
71
75
78
80
81
84
85
88
90
92
94

result:

ok 

Test #20:

score: 12
Accepted
time: 1ms
memory: 3668kb

input:

100
2 38 E
6 6 N
8 22 N
4 32 E
0 20 N
2 14 E
6 30 N
6 20 W
4 20 S
2 22 W
8 30 S
2 8 N
0 24 S
8 38 S
0 32 W
4 0 E
6 14 W
0 16 W
8 8 E
8 10 W
0 38 S
0 10 N
2 26 W
8 6 E
0 8 E
8 32 N
4 10 S
6 28 E
0 36 S
4 30 S
0 14 N
2 0 W
0 6 W
6 18 W
4 28 S
6 2 E
6 38 W
4 8 S
6 12 N
0 4 E
4 36 E
4 24 E
6 26 W
8 12 E...

output:

1
3
8
9
10
14
15
16
17
18
19
21
22
24
25
28
29
31
33
34
35
36
40
41
44
49
52
53
57
58
60
65
70
71
76
77
82
83
87
88
89
96
98
100

result:

ok 

Test #21:

score: 12
Accepted
time: 1ms
memory: 3620kb

input:

100
4 12 S
8 8 N
4 14 N
2 18 N
8 12 E
0 16 W
2 4 W
4 28 S
4 36 N
4 18 N
4 16 N
0 0 S
8 26 N
2 36 N
2 30 E
8 10 N
4 32 E
2 32 N
4 38 W
0 8 E
4 30 E
6 4 E
8 36 W
8 28 S
6 32 N
0 18 S
4 22 S
4 2 W
2 12 S
8 16 S
8 14 W
0 26 W
0 34 E
0 24 W
0 32 S
8 34 S
6 26 E
0 38 N
4 0 W
6 28 N
4 8 S
0 14 N
2 0 E
6 34...

output:

5
6
10
11
13
16
19
20
22
26
29
32
33
34
37
42
50
51
55
56
60
63
64
71
72
76
78
79
83
84
90
91
93
94
98
99

result:

ok 

Test #22:

score: 12
Accepted
time: 1ms
memory: 3648kb

input:

100
8 20 W
4 38 E
2 12 N
0 10 S
8 12 S
2 10 N
2 24 E
0 28 N
2 38 N
4 28 E
2 20 N
0 18 S
2 36 N
6 38 W
4 32 E
8 28 W
0 6 S
8 22 E
6 4 W
4 16 N
0 0 S
4 26 W
6 10 N
2 2 E
0 34 E
6 32 N
4 24 E
8 8 N
8 32 E
8 16 N
4 4 S
8 4 S
8 2 E
4 36 S
0 32 W
4 10 S
2 34 W
6 6 S
6 14 S
4 14 S
2 14 W
4 34 E
0 30 S
2 26...

output:

1
3
7
9
12
18
21
28
29
31
33
34
35
41
45
47
50
52
57
60
63
65
68
72
75
76
78
80
84
85
86
87
92
94
95
100

result:

ok 

Test #23:

score: 12
Accepted
time: 1ms
memory: 3692kb

input:

100
2 30 W
2 18 W
0 38 S
6 26 N
8 22 S
2 32 E
4 2 E
6 6 N
2 6 N
2 26 N
2 22 E
8 28 N
0 4 S
0 16 W
6 38 S
6 4 S
4 8 S
2 0 E
0 32 N
6 34 N
2 28 S
4 30 S
0 2 S
4 0 S
4 36 N
0 34 W
8 18 S
4 26 W
4 6 N
6 22 W
6 12 E
8 38 S
4 18 W
8 16 W
4 34 E
8 6 N
8 14 W
2 14 S
0 18 E
4 14 N
6 24 S
6 36 S
8 8 E
6 0 N
8...

output:

3
9
14
15
18
21
23
26
28
30
32
33
35
37
42
43
44
47
53
57
58
63
65
69
73
75
81
83
84
85
87
88
90
92
94
95
96
97
98

result:

ok 

Subtask #3:

score: 8
Accepted

Dependency #2:

100%
Accepted

Test #24:

score: 8
Accepted
time: 1ms
memory: 3936kb

input:

100
55730 78040 N
63588 61556 N
44452 89318 W
70518 63252 W
63870 69900 N
20558 13736 W
30676 3618 N
46556 87214 N
52984 80786 N
51668 82102 W
31696 2598 W
93292 40478 N
79566 54204 N
46984 86786 W
90284 34962 N
37124 96646 W
38832 94938 W
85994 47776 W
71794 61976 N
89082 44688 N
60614 73156 N
7647...

output:


result:

ok 

Test #25:

score: 8
Accepted
time: 1ms
memory: 3972kb

input:

100
89110 38332 W
42340 85102 W
47418 80024 W
36474 90968 W
11938 13920 W
32012 6604 W
31220 96222 N
12142 13716 W
28714 98728 N
47380 80062 N
20394 5464 N
97828 29614 W
9938 15920 N
17380 8478 W
10590 15268 W
3890 21968 W
8526 17332 N
51116 76326 N
780 25078 W
23234 2624 N
4140 21718 N
49462 77980 ...

output:


result:

ok 

Test #26:

score: 8
Accepted
time: 1ms
memory: 3812kb

input:

100
10138 25622 N
12350 94320 S
68742 84806 N
73166 78152 W
53518 51538 N
83720 65326 S
81334 87838 N
69820 4332 S
69138 91530 W
86906 38254 N
25342 21074 N
23272 16252 E
5752 87852 W
67080 1234 S
74952 7542 W
86348 8834 N
62828 43150 S
86604 90224 W
6126 20522 N
51694 71626 W
42958 83600 E
13780 84...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

result:

ok 

Test #27:

score: 8
Accepted
time: 1ms
memory: 3944kb

input:

100
70604 7840 W
88940 45568 W
194 75976 S
38568 51448 N
72120 46152 N
38612 66590 E
62926 10054 N
39128 81952 S
98506 14260 S
42086 41668 N
67944 35330 E
29958 62258 E
86268 1596 W
35940 56784 S
20480 59980 E
98806 10992 W
60714 55652 W
65056 14044 W
35222 82646 S
26772 58918 N
95446 42006 S
62272 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

result:

ok 

Test #28:

score: 8
Accepted
time: 1ms
memory: 3724kb

input:

100
4962 87014 W
56952 20966 S
79906 44760 N
71132 3734 S
48274 99414 E
96384 63090 N
46686 63154 E
91934 52946 S
73082 3184 E
75820 95966 E
80582 84570 S
25330 5670 N
72038 65094 E
67754 71728 W
22160 67544 N
59072 98152 S
88728 38842 W
24380 87238 S
70220 16454 W
31884 23260 E
27962 29112 N
11678 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

result:

ok 

Test #29:

score: 8
Accepted
time: 1ms
memory: 3616kb

input:

100
6 26 E
4 6 N
2 38 N
0 30 N
8 20 W
4 10 S
6 14 S
0 24 E
6 18 N
4 20 W
0 34 S
4 32 W
4 38 N
6 4 E
0 14 N
2 6 N
2 26 E
2 14 W
0 28 W
8 28 N
0 0 E
2 30 S
6 8 W
8 36 S
4 18 E
8 14 E
8 16 N
2 20 E
4 0 E
8 34 S
2 32 N
6 16 N
6 38 N
8 8 S
0 2 N
8 0 E
4 14 S
4 28 W
8 22 E
2 16 E
4 2 E
2 34 W
0 8 W
6 0 N
...

output:

2
3
4
5
8
9
11
14
17
19
24
26
27
29
30
35
36
39
41
42
43
44
45
46
49
63
67
69
71
72
74
77
78
79
80
81
83
87
91
97
99
100

result:

ok 

Test #30:

score: 8
Accepted
time: 1ms
memory: 3672kb

input:

100
8 20 E
0 16 S
4 30 W
6 6 S
6 22 E
0 20 S
4 2 S
2 34 W
8 26 N
8 32 E
0 30 E
0 22 E
0 38 E
4 24 E
4 18 S
8 8 N
0 10 E
2 16 N
8 14 N
0 12 N
2 20 E
6 36 E
6 16 S
4 38 W
4 4 W
2 38 S
4 16 W
8 24 S
4 32 N
6 24 W
2 18 N
8 12 N
8 4 E
8 10 W
0 18 S
2 36 N
0 14 W
4 36 W
2 0 W
4 20 N
6 34 N
2 6 E
8 16 E
6 ...

output:

1
2
6
7
10
26
32
33
35
37
39
43
46
50
56
58
60
63
67
75
76
79
81
85
89
94
95
96
98

result:

ok 

Test #31:

score: 8
Accepted
time: 1ms
memory: 3688kb

input:

100
0 34 E
8 36 N
6 14 W
4 26 W
2 26 W
0 16 S
0 2 S
6 18 N
0 20 N
2 6 E
8 32 W
0 24 E
0 4 N
6 0 N
0 8 W
2 2 N
6 20 E
6 22 W
2 32 S
8 10 S
8 6 E
2 34 S
8 34 E
4 20 S
4 0 E
4 38 S
8 22 W
4 34 N
2 14 E
8 16 N
2 12 E
6 2 N
2 28 E
8 4 S
4 32 W
8 8 S
8 2 N
0 22 S
0 18 N
0 14 W
4 36 N
8 20 N
0 30 N
8 14 S
...

output:

5
9
14
15
16
17
21
22
23
26
27
28
33
37
40
41
45
48
53
61
63
65
67
69
70
71
72
73
75
81
83
84
90
93
94
95
100

result:

ok 

Test #32:

score: 8
Accepted
time: 1ms
memory: 3688kb

input:

100
2 2 N
8 28 N
2 28 N
8 10 N
4 28 E
4 34 W
6 14 W
4 30 N
4 4 S
2 34 W
6 18 N
0 24 E
2 14 E
4 32 S
2 36 E
8 32 E
2 12 E
0 0 N
8 30 N
6 10 N
4 10 W
4 16 N
2 0 N
8 22 E
0 34 N
0 36 W
8 38 E
8 26 W
6 36 W
6 16 N
6 34 W
6 38 S
8 0 S
4 12 E
0 28 W
6 4 W
2 32 S
0 8 S
0 14 W
8 6 S
6 26 S
2 20 E
4 14 E
0 4...

output:

10
11
16
18
19
21
23
24
25
26
27
32
35
39
45
46
50
51
52
56
57
58
62
63
64
66
69
70
73
75
78
81
82
83
84
85
86
89
92
95
96
97
98
100

result:

ok 

Test #33:

score: 8
Accepted
time: 1ms
memory: 3672kb

input:

100
0 18 E
0 12 W
8 8 W
0 2 N
0 38 S
4 36 E
6 2 W
4 26 N
6 36 W
2 24 S
8 18 E
8 12 N
2 32 W
4 28 W
2 18 E
4 34 S
0 34 S
8 28 S
0 22 N
4 0 N
4 22 E
2 12 E
2 28 W
6 0 N
2 16 S
2 14 N
0 10 S
8 24 E
2 2 E
8 32 N
8 4 N
0 24 W
2 0 S
6 24 E
8 30 N
2 38 W
6 16 N
8 10 N
2 30 N
8 20 N
0 8 E
4 38 S
6 10 N
8 14...

output:

2
4
5
10
11
12
13
17
20
22
23
24
26
27
28
30
32
34
36
38
42
51
52
60
64
66
70
72
73
74
75
76
79
81
84
90
92
93
98
100

result:

ok 

Subtask #4:

score: 11
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #34:

score: 11
Accepted
time: 1ms
memory: 3908kb

input:

200
418707804 884434338 N
555991098 928743606 W
392083690 430592748 W
698318694 647664350 N
628346348 194330090 W
584668884 977074926 N
671813258 150863180 N
682186188 620955954 N
635355860 926387950 N
710571802 851172008 W
829084908 516898136 W
547697376 274979062 N
493718438 991016266 N
874643460 ...

output:


result:

ok 

Test #35:

score: 11
Accepted
time: 1ms
memory: 4124kb

input:

200
847227196 820455410 N
7504288 76298524 N
751161348 916521258 N
231937054 366177574 W
478897096 119217532 N
518375114 79739514 N
335464316 262650312 N
65495114 18307698 W
211213756 386900872 N
79343914 4458898 W
414728052 183386576 W
31940314 51862498 N
307592722 290521906 N
471142204 126972424 W...

output:


result:

ok 

Test #36:

score: 11
Accepted
time: 1ms
memory: 4084kb

input:

200
937922402 479776042 N
737800950 669865080 N
94805170 786037934 N
279746956 772502456 N
839034342 860639288 S
728946458 157523896 N
526290022 279816454 N
666552716 909472406 S
339809716 124530126 S
691515652 699889668 E
243448022 372701686 W
40705500 565704662 W
234888440 753665074 E
999020110 79...

output:


result:

ok 

Test #37:

score: 11
Accepted
time: 0ms
memory: 4148kb

input:

200
995999350 525531220 S
771273924 486313170 E
801521866 212496224 E
842601274 967310936 W
697173728 308932872 S
514384138 863306956 E
688208648 451164400 W
4055886 291549990 E
442157654 665686428 E
982849734 467740562 N
785429168 348853242 S
715944898 416902070 S
99245012 894514728 E
833840070 261...

output:


result:

ok 

Test #38:

score: 11
Accepted
time: 1ms
memory: 3900kb

input:

200
401533264 133551616 W
495086744 491731536 S
880037162 520197302 N
363177994 882753098 S
296457894 617495150 W
810026496 471602802 W
295788616 70005724 N
914121936 334621246 E
962136934 9787394 S
293673484 191965774 S
661172796 323578246 S
818763068 947754102 S
640808176 647808156 E
517530886 183...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #39:

score: 11
Accepted
time: 0ms
memory: 3988kb

input:

200
525664546 412363198 E
909814220 642373718 E
543300502 244470052 E
622069396 666730138 N
90088532 951020440 W
839792914 179824668 E
417475036 86373024 W
642976434 584508552 N
805709716 443000254 W
966217702 390830980 S
761538128 736216542 N
334614868 111893978 W
62995774 156400960 E
404867350 261...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #40:

score: 11
Accepted
time: 1ms
memory: 3924kb

input:

200
554261220 990433238 W
848708254 150721804 W
620691606 804513644 W
117305592 369401062 W
206334656 16987934 S
701896230 442280398 N
15947918 237986778 S
799544510 473710284 W
171408440 793114152 E
247006190 762387132 W
276509060 936608066 S
777366706 76339550 E
469787190 686521590 E
401275090 604...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #41:

score: 11
Accepted
time: 1ms
memory: 3920kb

input:

200
2 30 W
2 0 S
2 12 E
10 32 N
8 0 S
0 0 W
10 28 W
12 54 E
2 28 S
12 8 N
2 50 S
8 52 E
10 8 N
8 44 N
0 28 S
0 18 W
2 38 W
14 0 E
12 46 N
12 48 E
6 0 N
6 38 E
4 36 S
10 36 W
12 12 N
8 38 E
4 44 E
8 46 E
4 46 S
8 12 W
4 38 N
12 40 S
0 46 W
10 16 S
2 52 E
8 6 E
12 18 S
0 32 W
14 6 W
2 20 E
0 30 N
0 52...

output:

1
3
6
8
11
16
17
18
20
21
24
26
33
38
42
58
59
64
70
72
79
80
91
93
97
98
101
104
105
109
110
111
117
119
124
127
129
134
149
152
155
158
161
163
167
168
173
175
177
180
181
188
189
190
199

result:

ok 

Test #42:

score: 11
Accepted
time: 1ms
memory: 3656kb

input:

200
6 16 N
2 0 N
0 16 W
12 40 E
6 12 S
10 6 W
6 44 N
0 38 N
2 10 W
4 38 W
4 16 N
12 26 S
4 42 N
2 38 N
12 8 S
2 42 E
8 8 E
4 24 N
6 18 W
6 54 W
12 44 S
8 36 E
2 2 S
8 42 S
2 22 N
2 34 S
8 40 W
0 52 E
0 14 S
8 46 S
6 42 S
6 50 W
12 18 N
0 8 N
4 50 W
10 28 S
10 12 W
4 26 E
10 52 W
4 22 N
6 14 E
0 32 W...

output:

2
3
4
10
16
18
20
27
40
41
42
45
47
48
50
52
58
66
70
74
82
84
85
86
87
90
93
94
96
101
103
107
109
111
112
114
116
118
121
123
124
128
134
136
138
139
140
143
147
148
150
155
163
175
177
180
181
182
183
189
190
194
199

result:

ok 

Test #43:

score: 11
Accepted
time: 1ms
memory: 3712kb

input:

200
0 54 E
4 14 W
2 8 W
6 20 W
4 24 W
6 48 N
4 16 W
8 0 W
0 26 N
4 54 N
10 24 N
8 48 W
4 42 W
2 50 N
12 10 E
6 28 N
8 36 S
8 4 S
10 36 W
4 18 N
4 44 S
0 42 W
6 16 S
0 12 W
0 50 S
2 34 E
2 32 N
12 20 W
8 50 E
4 36 S
6 4 S
10 12 E
4 26 W
0 22 E
4 52 N
0 46 W
6 10 S
0 36 W
6 40 E
6 54 N
6 38 S
12 34 N
...

output:

2
4
7
14
15
19
22
24
25
26
28
29
31
32
36
37
38
41
42
44
46
48
49
51
52
53
54
55
57
58
59
63
65
73
74
76
77
79
81
83
84
86
87
88
89
91
95
99
101
102
103
105
106
107
110
112
119
123
133
137
138
139
141
144
156
160
166
168
173
180
181
184
185
188
193
199

result:

ok 

Test #44:

score: 11
Accepted
time: 1ms
memory: 3708kb

input:

200
12 38 S
10 40 E
10 52 W
12 48 W
4 12 E
10 54 S
6 34 N
4 22 N
4 16 N
4 54 W
4 32 W
4 50 W
12 4 S
8 4 E
12 40 S
10 26 E
12 24 E
2 8 E
12 46 N
14 4 E
4 14 W
6 24 E
0 50 W
10 30 W
8 14 S
12 2 E
2 26 W
12 30 W
2 28 N
0 2 S
0 6 N
4 20 S
6 40 W
2 4 S
6 20 S
6 12 W
2 24 W
2 44 N
14 2 E
4 36 E
12 32 N
0 ...

output:

6
9
10
12
14
17
19
20
23
25
26
27
29
37
39
41
44
45
47
49
53
61
62
67
68
69
70
72
73
74
78
79
80
94
96
100
108
109
110
114
116
117
118
120
121
124
125
126
129
136
138
149
155
156
160
164
166
167
170
177
184
191
192
193
195
196

result:

ok 

Test #45:

score: 11
Accepted
time: 1ms
memory: 3720kb

input:

200
2 2 S
4 2 E
0 22 N
6 12 W
2 14 N
0 26 E
0 32 S
0 42 W
10 52 W
10 28 N
4 4 N
8 16 N
12 54 W
6 8 W
8 52 S
10 48 W
6 48 W
0 30 N
10 8 N
4 8 W
6 10 W
2 44 W
8 20 N
10 22 S
6 28 S
6 44 N
8 28 S
4 40 W
0 48 E
4 16 N
4 14 E
8 2 N
2 4 W
6 36 W
6 4 E
12 16 W
4 52 W
6 24 E
8 24 S
12 34 S
10 50 N
2 20 E
0 ...

output:

8
9
12
14
16
30
32
33
36
37
39
45
46
49
53
55
60
63
65
67
72
77
81
82
93
96
97
101
110
113
115
121
124
139
140
147
154
156
158
162
164
166
173
176
177
180
181
184
187
190
191
194
197
198

result:

ok 

Subtask #5:

score: 9
Accepted

Dependency #4:

100%
Accepted

Test #46:

score: 9
Accepted
time: 39ms
memory: 10244kb

input:

5000
57068244 113807472 W
4951696 165924020 N
93428958 77446758 N
42885696 830234676 N
61671068 109204648 W
100613650 70262066 N
851013512 22106860 N
864688770 8431602 W
101367302 69508414 N
511091658 568942730 N
147333652 23542064 N
87293646 83582070 W
109225338 61650378 W
94224988 76650728 N
11031...

output:


result:

ok 

Test #47:

score: 9
Accepted
time: 33ms
memory: 10528kb

input:

5000
7137048 14604888 W
61784660 167645486 N
244888398 275295214 W
211457288 17972858 N
184364260 45065886 W
221194886 8235260 W
61803656 167626490 N
189772138 39658008 N
205628820 23801326 W
20658910 1083026 W
15742914 5999022 W
352628718 167554894 N
19414966 500768646 W
61184318 168245828 W
269698...

output:


result:

ok 

Test #48:

score: 9
Accepted
time: 26ms
memory: 11448kb

input:

5000
884665042 142832368 N
734811284 817438040 W
935054430 608811298 S
292569654 55273198 S
55213876 492140634 S
301458534 134620984 N
777571150 182088732 N
528748980 152604850 N
780122946 898587112 S
911048382 338266060 E
455984470 543330264 W
826464062 964907170 N
860904864 984380294 W
391170450 4...

output:


result:

ok 

Test #49:

score: 9
Accepted
time: 34ms
memory: 11460kb

input:

5000
963605568 409757598 N
343090188 200793180 W
219712636 554528814 S
991137434 164386004 E
645723338 753025612 S
587572374 846162408 E
842234086 977706846 E
216692912 471749130 S
106500158 538745870 N
349825312 723195584 N
353285418 942704488 S
297657128 543212440 S
382242660 80122494 N
568077828 ...

output:


result:

ok 

Test #50:

score: 9
Accepted
time: 28ms
memory: 12104kb

input:

5000
816454036 580948656 W
457522768 438394172 W
294452460 646945782 S
872717614 384665198 E
965152664 429230356 N
648438716 868214656 W
715141742 476443312 S
981289070 776309634 S
632999024 180491142 E
301364460 803130922 E
380870632 578003552 W
338254858 576254140 S
589559862 575536628 W
520800776...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #51:

score: 9
Accepted
time: 24ms
memory: 12040kb

input:

5000
554852842 574658278 W
97700860 557808744 S
817010386 301464158 W
656113494 790284870 W
985009902 829820920 S
451951710 996144394 N
548800700 362130304 S
206715584 771217012 E
565816976 101308386 W
747008664 732029384 W
167735736 886527684 W
978884560 146942978 E
658297210 911245082 S
952754092 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #52:

score: 9
Accepted
time: 30ms
memory: 12108kb

input:

5000
143339376 315581010 W
282222312 663669058 W
822833684 226553100 N
476188174 198207038 E
703575814 662216578 S
284885546 978368754 S
134049568 976398808 E
20453372 717921430 N
667627878 663877508 S
375932814 801150760 W
977744060 518448458 S
470532536 477971434 N
411645432 493163110 E
604305832 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 

Test #53:

score: 9
Accepted
time: 24ms
memory: 4872kb

input:

5000
24 252 S
34 218 E
30 148 W
52 168 S
32 176 N
24 130 N
12 190 N
30 266 S
64 146 N
44 82 W
30 134 E
2 146 N
4 210 N
54 164 N
6 74 E
6 234 S
14 120 E
2 0 E
42 234 S
62 202 W
68 262 N
32 260 S
24 242 S
66 186 N
6 226 S
20 206 S
22 140 E
50 176 S
30 102 E
48 44 S
14 132 S
48 126 S
16 100 S
16 36 E
3...

output:

40
44
56
68
114
130
141
149
154
158
171
172
176
177
185
211
212
214
217
223
226
233
238
239
248
269
291
306
318
328
343
354
365
393
419
453
458
469
483
486
497
508
514
517
522
525
536
555
562
566
569
581
588
598
609
613
617
619
633
637
646
651
668
683
691
697
698
711
720
724
746
748
751
752
755
772
...

result:

ok 

Test #54:

score: 9
Accepted
time: 20ms
memory: 5112kb

input:

5000
58 0 W
26 264 N
50 180 S
34 222 S
22 14 N
18 140 E
8 4 W
26 114 W
68 248 S
12 224 E
56 182 S
24 206 E
38 270 E
46 120 W
50 188 S
18 252 E
60 206 E
18 218 E
68 120 S
6 56 E
10 100 E
14 260 W
30 276 N
32 248 N
54 88 E
50 58 N
30 52 S
48 226 N
20 62 W
42 8 W
30 116 N
58 280 S
14 212 N
36 210 N
48 ...

output:

17
22
29
32
34
55
56
60
63
68
73
94
100
103
115
124
128
135
139
148
151
152
155
158
167
189
226
235
255
264
273
281
283
287
293
306
310
311
315
330
331
340
349
360
378
387
393
423
429
435
437
444
458
463
485
488
490
493
500
502
504
507
509
530
537
550
556
561
566
623
625
627
631
640
646
664
697
702
...

result:

ok 

Test #55:

score: 9
Accepted
time: 24ms
memory: 4824kb

input:

5000
40 18 N
68 142 E
20 268 N
24 2 W
62 34 S
2 154 S
64 176 E
48 208 W
8 4 E
6 48 E
28 232 W
32 154 S
22 114 W
60 16 W
22 278 W
12 102 W
50 18 W
14 154 N
48 0 W
32 22 E
66 38 S
54 60 N
6 218 W
60 238 N
6 112 S
22 138 N
46 130 S
58 224 E
50 84 N
8 10 W
46 222 S
52 152 E
30 118 S
62 88 S
10 180 N
64 ...

output:

2
15
16
19
20
28
35
52
55
64
67
73
75
76
87
110
120
121
128
129
141
145
152
167
170
174
179
181
189
207
209
210
225
226
228
231
232
239
249
252
255
270
275
316
327
335
341
348
351
381
382
396
398
399
408
413
435
441
443
477
514
525
528
531
541
561
584
585
594
603
605
607
619
636
661
668
669
681
686
...

result:

ok 

Test #56:

score: 9
Accepted
time: 24ms
memory: 4944kb

input:

5000
20 98 E
58 234 W
32 180 N
34 278 N
48 160 N
2 136 S
68 154 W
38 108 E
14 42 S
32 62 S
20 240 S
68 92 E
28 106 S
6 140 S
0 196 S
20 4 N
16 56 N
42 134 W
50 104 E
6 150 S
62 164 W
42 48 N
32 278 S
0 232 N
16 6 W
52 252 E
54 96 S
54 58 E
26 54 S
24 68 W
58 18 N
66 134 W
34 150 N
28 152 S
70 34 W
5...

output:

12
16
17
26
59
62
65
77
90
92
94
96
97
100
102
105
120
121
124
128
129
142
145
152
154
162
170
176
200
213
215
217
241
253
255
265
271
281
286
297
302
305
307
308
330
337
343
348
377
400
403
422
435
443
445
453
456
478
498
504
522
530
549
558
561
566
570
586
599
601
618
621
624
638
670
679
684
696
7...

result:

ok 

Test #57:

score: 9
Accepted
time: 24ms
memory: 4960kb

input:

5000
52 176 S
4 172 W
20 110 W
60 148 E
4 226 E
22 26 E
26 44 N
58 262 W
22 160 E
36 228 S
36 124 W
52 222 S
36 194 E
48 6 W
70 124 E
12 218 S
56 238 N
58 196 W
42 128 E
58 168 S
18 166 S
22 212 E
12 76 S
52 70 N
0 20 E
60 74 E
32 118 W
6 16 E
0 186 S
28 128 S
64 120 E
32 76 N
38 88 E
4 174 N
46 246...

output:

15
31
38
39
42
56
89
94
104
105
117
127
132
164
173
181
184
188
192
203
213
240
246
264
266
318
326
332
349
350
357
365
398
409
421
432
435
454
462
468
479
480
492
497
510
511
525
531
539
553
555
559
565
595
597
611
613
617
627
631
640
684
685
686
690
691
696
699
705
713
722
725
727
734
743
766
770
...

result:

ok 

Subtask #6:

score: 0
Time Limit Exceeded

Test #58:

score: 0
Time Limit Exceeded

input:

200000
526715640 430855204 E
731546662 226024182 S
254814720 702756124 E
227354364 730216480 S
764250602 193320242 S
150102088 807468756 E
204858572 752712272 S
635512190 322058654 E
403910248 553660596 S
257917918 4587926 S
949444340 8126504 S
907805098 49765746 S
553836306 403734538 S
40977864 617...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%