oj.uz

Submission #703100

# Submission time Handle Problem Language Result Execution time Memory
703100 2023-02-26T06:12:20 Z Cyanmond Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 463 ms 15808 KB 
#include <bits/stdc++.h>

struct Point {
    int r, c;
};
auto compPoint = [](Point a, Point b) {
    return std::make_pair(a.r, a.c) < std::make_pair(b.r, b.c);
};

std::pair<int, int> dxy[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

int main() {
    int N, T;
    std::cin >> N >> T;
    std::vector<Point> sks(N);
    for (auto &[r, c] : sks) {
        std::cin >> r >> c;
    }
    std::map<Point, int, decltype(compPoint)> skMap(compPoint);
    for (int i = 0; i < N; ++i) {
        skMap[sks[i]] = i;
    }

    std::vector<bool> isSeen(N);
    std::vector<int> answer;
    std::priority_queue<Point, std::vector<Point>, decltype(compPoint)> que(compPoint);
    int minV = 0;
    for (int i = 1; i < N; ++i) {
        if (compPoint(sks[i], sks[minV])) {
            minV = i;
        }
    }
    que.push(sks[minV]);
    isSeen[minV] = true;
    while (not que.empty()) {
        const auto [r, c] = que.top();
        que.pop();
        const int f = skMap[{r, c}];
        answer.push_back(f);
        for (const auto &[ar, ac] : dxy) {
            const int nr = r + ar, nc = c + ac;
            auto itr = skMap.find({nr, nc});
            if (itr == skMap.end()) {
                continue;
            }
            const int t = itr->second;
            if (isSeen[t]) {
                continue;
            }
            isSeen[t] = true;
            que.push({nr, nc});
        }
    }

    if (answer.size() != N) {
        std::cout << "NO" << std::endl;
        return 0;
    }
    std::cout << "YES" << std::endl;
    for (const auto e : answer) {
        std::cout << e + 1 << std::endl;
    }
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:55:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if (answer.size() != N) {
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 212 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 212 KB ans=YES N=5
5 Correct 0 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 KB ans=YES N=5
7 Correct 0 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 0 ms 212 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 212 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 212 KB ans=YES N=5
5 Correct 0 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 KB ans=YES N=5
7 Correct 0 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 0 ms 212 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 0 ms 212 KB ans=YES N=17
18 Correct 0 ms 212 KB ans=YES N=25
19 Correct 1 ms 212 KB ans=YES N=100
20 Correct 1 ms 212 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 212 KB ans=YES N=90
23 Correct 1 ms 212 KB ans=YES N=63
24 Correct 1 ms 212 KB ans=YES N=87
25 Correct 1 ms 304 KB ans=YES N=183
26 Correct 1 ms 212 KB ans=YES N=188
27 Correct 1 ms 212 KB ans=YES N=183
28 Correct 1 ms 212 KB ans=YES N=189
29 Correct 1 ms 212 KB ans=YES N=200
30 Correct 1 ms 304 KB ans=YES N=190
31 Correct 1 ms 212 KB ans=YES N=187
32 Correct 1 ms 212 KB ans=YES N=187
33 Correct 1 ms 212 KB ans=YES N=182
34 Correct 1 ms 212 KB ans=YES N=184
35 Correct 1 ms 212 KB ans=YES N=188
36 Correct 1 ms 212 KB ans=YES N=181
37 Correct 1 ms 212 KB ans=YES N=188
38 Correct 1 ms 212 KB ans=YES N=191
39 Correct 1 ms 212 KB ans=YES N=196
40 Correct 1 ms 212 KB ans=YES N=196
41 Correct 1 ms 304 KB ans=YES N=196
42 Correct 1 ms 308 KB ans=YES N=196
43 Correct 1 ms 212 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 212 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 212 KB ans=YES N=5
5 Correct 0 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 KB ans=YES N=5
7 Correct 0 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 0 ms 212 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 0 ms 212 KB ans=YES N=17
18 Correct 0 ms 212 KB ans=YES N=25
19 Correct 1 ms 212 KB ans=YES N=100
20 Correct 1 ms 212 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 212 KB ans=YES N=90
23 Correct 1 ms 212 KB ans=YES N=63
24 Correct 1 ms 212 KB ans=YES N=87
25 Correct 1 ms 304 KB ans=YES N=183
26 Correct 1 ms 212 KB ans=YES N=188
27 Correct 1 ms 212 KB ans=YES N=183
28 Correct 1 ms 212 KB ans=YES N=189
29 Correct 1 ms 212 KB ans=YES N=200
30 Correct 1 ms 304 KB ans=YES N=190
31 Correct 1 ms 212 KB ans=YES N=187
32 Correct 1 ms 212 KB ans=YES N=187
33 Correct 1 ms 212 KB ans=YES N=182
34 Correct 1 ms 212 KB ans=YES N=184
35 Correct 1 ms 212 KB ans=YES N=188
36 Correct 1 ms 212 KB ans=YES N=181
37 Correct 1 ms 212 KB ans=YES N=188
38 Correct 1 ms 212 KB ans=YES N=191
39 Correct 1 ms 212 KB ans=YES N=196
40 Correct 1 ms 212 KB ans=YES N=196
41 Correct 1 ms 304 KB ans=YES N=196
42 Correct 1 ms 308 KB ans=YES N=196
43 Correct 1 ms 212 KB ans=YES N=195
44 Correct 2 ms 480 KB ans=NO N=1934
45 Correct 2 ms 340 KB ans=NO N=1965
46 Correct 5 ms 468 KB ans=YES N=1824
47 Correct 5 ms 468 KB ans=YES N=1981
48 Correct 7 ms 340 KB ans=YES N=1814
49 Correct 5 ms 444 KB ans=YES N=1854
50 Correct 5 ms 468 KB ans=YES N=1831
51 Correct 6 ms 444 KB ans=YES N=2000
52 Correct 6 ms 444 KB ans=YES N=1847
53 Correct 6 ms 484 KB ans=YES N=1819
54 Correct 5 ms 468 KB ans=YES N=1986
55 Correct 6 ms 568 KB ans=YES N=2000
56 Correct 5 ms 440 KB ans=YES N=1834
57 Correct 6 ms 468 KB ans=YES N=1860
58 Correct 5 ms 468 KB ans=YES N=1898
59 Correct 5 ms 440 KB ans=YES N=1832
60 Correct 6 ms 444 KB ans=YES N=1929
61 Correct 5 ms 440 KB ans=YES N=1919
62 Correct 5 ms 484 KB ans=YES N=1882
63 Correct 6 ms 492 KB ans=YES N=1922
64 Correct 5 ms 444 KB ans=YES N=1989
65 Correct 5 ms 440 KB ans=YES N=1978
66 Correct 5 ms 448 KB ans=YES N=1867
67 Correct 7 ms 468 KB ans=YES N=1942

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB ans=NO N=1934
2 Correct 2 ms 340 KB ans=NO N=1965
3 Incorrect 4 ms 340 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 585)
4 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 212 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 212 KB ans=YES N=5
5 Correct 0 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 KB ans=YES N=5
7 Correct 0 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 0 ms 212 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 0 ms 212 KB ans=YES N=17
18 Correct 0 ms 212 KB ans=YES N=25
19 Correct 1 ms 212 KB ans=YES N=100
20 Correct 1 ms 212 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 212 KB ans=YES N=90
23 Correct 1 ms 212 KB ans=YES N=63
24 Correct 1 ms 212 KB ans=YES N=87
25 Correct 1 ms 304 KB ans=YES N=183
26 Correct 1 ms 212 KB ans=YES N=188
27 Correct 1 ms 212 KB ans=YES N=183
28 Correct 1 ms 212 KB ans=YES N=189
29 Correct 1 ms 212 KB ans=YES N=200
30 Correct 1 ms 304 KB ans=YES N=190
31 Correct 1 ms 212 KB ans=YES N=187
32 Correct 1 ms 212 KB ans=YES N=187
33 Correct 1 ms 212 KB ans=YES N=182
34 Correct 1 ms 212 KB ans=YES N=184
35 Correct 1 ms 212 KB ans=YES N=188
36 Correct 1 ms 212 KB ans=YES N=181
37 Correct 1 ms 212 KB ans=YES N=188
38 Correct 1 ms 212 KB ans=YES N=191
39 Correct 1 ms 212 KB ans=YES N=196
40 Correct 1 ms 212 KB ans=YES N=196
41 Correct 1 ms 304 KB ans=YES N=196
42 Correct 1 ms 308 KB ans=YES N=196
43 Correct 1 ms 212 KB ans=YES N=195
44 Correct 2 ms 480 KB ans=NO N=1934
45 Correct 2 ms 340 KB ans=NO N=1965
46 Correct 5 ms 468 KB ans=YES N=1824
47 Correct 5 ms 468 KB ans=YES N=1981
48 Correct 7 ms 340 KB ans=YES N=1814
49 Correct 5 ms 444 KB ans=YES N=1854
50 Correct 5 ms 468 KB ans=YES N=1831
51 Correct 6 ms 444 KB ans=YES N=2000
52 Correct 6 ms 444 KB ans=YES N=1847
53 Correct 6 ms 484 KB ans=YES N=1819
54 Correct 5 ms 468 KB ans=YES N=1986
55 Correct 6 ms 568 KB ans=YES N=2000
56 Correct 5 ms 440 KB ans=YES N=1834
57 Correct 6 ms 468 KB ans=YES N=1860
58 Correct 5 ms 468 KB ans=YES N=1898
59 Correct 5 ms 440 KB ans=YES N=1832
60 Correct 6 ms 444 KB ans=YES N=1929
61 Correct 5 ms 440 KB ans=YES N=1919
62 Correct 5 ms 484 KB ans=YES N=1882
63 Correct 6 ms 492 KB ans=YES N=1922
64 Correct 5 ms 444 KB ans=YES N=1989
65 Correct 5 ms 440 KB ans=YES N=1978
66 Correct 5 ms 448 KB ans=YES N=1867
67 Correct 7 ms 468 KB ans=YES N=1942
68 Correct 96 ms 6064 KB ans=NO N=66151
69 Correct 48 ms 5272 KB ans=NO N=64333
70 Correct 177 ms 6568 KB ans=YES N=69316
71 Correct 168 ms 6280 KB ans=YES N=66695
72 Correct 183 ms 6600 KB ans=YES N=68436
73 Correct 181 ms 6560 KB ans=YES N=70000
74 Correct 182 ms 6500 KB ans=YES N=68501
75 Correct 191 ms 6632 KB ans=YES N=70000
76 Correct 168 ms 6124 KB ans=YES N=65009
77 Correct 177 ms 6388 KB ans=YES N=67007
78 Correct 175 ms 6232 KB ans=YES N=66357
79 Correct 174 ms 6232 KB ans=YES N=65430
80 Correct 172 ms 6416 KB ans=YES N=65790
81 Correct 167 ms 6184 KB ans=YES N=66020
82 Correct 172 ms 6164 KB ans=YES N=65809
83 Correct 172 ms 6400 KB ans=YES N=65651
84 Correct 185 ms 6436 KB ans=YES N=68040
85 Correct 176 ms 6352 KB ans=YES N=66570
86 Correct 168 ms 6072 KB ans=YES N=65421
87 Correct 181 ms 6432 KB ans=YES N=68351
88 Correct 170 ms 6352 KB ans=YES N=67027
89 Correct 161 ms 6552 KB ans=YES N=68879
90 Correct 170 ms 6356 KB ans=YES N=67256
91 Correct 400 ms 13460 KB ans=YES N=148315
92 Correct 122 ms 11596 KB ans=NO N=142745
93 Correct 181 ms 13732 KB ans=NO N=148443
94 Correct 444 ms 15228 KB ans=YES N=148328
95 Correct 452 ms 15388 KB ans=YES N=147855
96 Correct 460 ms 15772 KB ans=YES N=150000
97 Correct 443 ms 15008 KB ans=YES N=144725
98 Correct 451 ms 15652 KB ans=YES N=149445
99 Correct 442 ms 15264 KB ans=YES N=144455
100 Correct 463 ms 14916 KB ans=YES N=143487
101 Correct 451 ms 15356 KB ans=YES N=149688
102 Correct 429 ms 14856 KB ans=YES N=141481
103 Correct 449 ms 15372 KB ans=YES N=147430
104 Correct 434 ms 14956 KB ans=YES N=142247
105 Correct 459 ms 15808 KB ans=YES N=149941
106 Correct 449 ms 14992 KB ans=YES N=141635
107 Correct 426 ms 14780 KB ans=YES N=142896
108 Correct 419 ms 14548 KB ans=YES N=142069
109 Correct 407 ms 14172 KB ans=YES N=142378
110 Correct 452 ms 15552 KB ans=YES N=150000
111 Correct 422 ms 14564 KB ans=YES N=141452
112 Correct 393 ms 13880 KB ans=YES N=134453
113 Correct 414 ms 14912 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5584 KB ans=NO N=66151
2 Correct 46 ms 4808 KB ans=NO N=64333
3 Incorrect 177 ms 6028 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 2522)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB ans=NO N=1934
2 Correct 2 ms 340 KB ans=NO N=1965
3 Incorrect 4 ms 340 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 585)
4 Halted 0 ms 0 KB -