oj.uz

Submission #533197

# Submission time Handle Problem Language Result Execution time Memory
533197 2022-03-05T06:25:37 Z wenqi Building Skyscrapers (CEOI19_skyscrapers) C++17
34 / 100
 67 ms 8388 KB 
// trans rights

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

using ll = long long;

#define M 1000000069

int N, T;
int X[150069];
int Y[150069];
unordered_map<ll, int> P;

int main(int argc, const char *argv[])
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> T;
    priority_queue<pair<int, int>> pq;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        X[i] = x;
        Y[i] = y;

        if (i == 1)
        {
            pq.push({0, i});
        }else{
            P[(ll) x * M + y] = i;
        }
    }
    vector<int> R;
    while (not pq.empty())
    {
        int i = pq.top().second;
        pq.pop();

        R.push_back(i);

        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                ll idx = (ll) (X[i] + x) * M + (Y[i] + y);
                if (P[idx])
                {
                    int j = P[idx];
                    pq.push({-abs(X[j] - X[1]) -abs(Y[j] - Y[1]), j});
                    P[idx] = 0;
                }
            }
        }
    }
    if (R.size() != N)
    {
        cout << "NO\n";
    }else{
        cout << "YES\n";

        for (int a : R)
            cout << a << '\n';
    }
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ans=YES N=1
2 Correct 0 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 0 ms 204 KB ans=YES N=5
5 Correct 1 ms 204 KB ans=YES N=9
6 Correct 0 ms 204 KB ans=YES N=5
7 Correct 0 ms 204 KB ans=NO N=9
8 Correct 0 ms 204 KB ans=NO N=10
9 Correct 1 ms 204 KB ans=YES N=10
10 Correct 0 ms 204 KB ans=YES N=10
11 Correct 1 ms 324 KB ans=YES N=10
12 Correct 1 ms 336 KB ans=YES N=9
13 Correct 1 ms 336 KB ans=YES N=9
14 Correct 1 ms 208 KB ans=YES N=8
15 Correct 1 ms 208 KB ans=YES N=8
16 Correct 0 ms 208 KB ans=NO N=2
17 Correct 1 ms 208 KB ans=YES N=17
18 Correct 1 ms 208 KB ans=YES N=25
19 Correct 1 ms 336 KB ans=YES N=100
20 Correct 1 ms 336 KB ans=YES N=185
21 Correct 1 ms 336 KB ans=NO N=174
22 Correct 1 ms 324 KB ans=YES N=90
23 Correct 1 ms 324 KB ans=YES N=63
24 Correct 1 ms 336 KB ans=YES N=87
25 Correct 1 ms 324 KB ans=YES N=183
26 Correct 1 ms 336 KB ans=YES N=188
27 Correct 1 ms 336 KB ans=YES N=183
28 Correct 1 ms 336 KB ans=YES N=189
29 Correct 1 ms 336 KB ans=YES N=200
30 Correct 1 ms 336 KB ans=YES N=190
31 Correct 1 ms 328 KB ans=YES N=187
32 Correct 1 ms 320 KB ans=YES N=187
33 Correct 1 ms 336 KB ans=YES N=182
34 Correct 1 ms 336 KB ans=YES N=184
35 Correct 1 ms 336 KB ans=YES N=188
36 Correct 1 ms 336 KB ans=YES N=181
37 Correct 1 ms 324 KB ans=YES N=188
38 Correct 1 ms 336 KB ans=YES N=191
39 Correct 0 ms 328 KB ans=YES N=196
40 Correct 1 ms 332 KB ans=YES N=196
41 Correct 1 ms 336 KB ans=YES N=196
42 Correct 1 ms 336 KB ans=YES N=196
43 Correct 1 ms 336 KB ans=YES N=195
44 Correct 1 ms 336 KB ans=NO N=1934
45 Correct 2 ms 336 KB ans=NO N=1965
46 Correct 3 ms 324 KB ans=YES N=1824
47 Correct 3 ms 464 KB ans=YES N=1981
48 Correct 2 ms 464 KB ans=YES N=1814
49 Correct 2 ms 460 KB ans=YES N=1854
50 Correct 3 ms 464 KB ans=YES N=1831
51 Correct 3 ms 464 KB ans=YES N=2000
52 Correct 3 ms 464 KB ans=YES N=1847
53 Correct 2 ms 464 KB ans=YES N=1819
54 Correct 3 ms 464 KB ans=YES N=1986
55 Correct 3 ms 592 KB ans=YES N=2000
56 Correct 3 ms 592 KB ans=YES N=1834
57 Correct 3 ms 592 KB ans=YES N=1860
58 Correct 3 ms 688 KB ans=YES N=1898
59 Correct 2 ms 592 KB ans=YES N=1832
60 Correct 4 ms 720 KB ans=YES N=1929
61 Correct 2 ms 464 KB ans=YES N=1919
62 Correct 3 ms 592 KB ans=YES N=1882
63 Correct 4 ms 720 KB ans=YES N=1922
64 Correct 2 ms 464 KB ans=YES N=1989
65 Correct 2 ms 592 KB ans=YES N=1978
66 Correct 2 ms 592 KB ans=YES N=1867
67 Correct 2 ms 592 KB ans=YES N=1942
68 Correct 51 ms 6368 KB ans=NO N=66151
69 Correct 18 ms 3928 KB ans=NO N=64333
70 Correct 67 ms 5436 KB ans=YES N=69316
71 Correct 43 ms 5204 KB ans=YES N=66695
72 Correct 43 ms 5468 KB ans=YES N=68436
73 Correct 45 ms 5556 KB ans=YES N=70000
74 Correct 47 ms 5452 KB ans=YES N=68501
75 Correct 42 ms 5464 KB ans=YES N=70000
76 Correct 51 ms 6388 KB ans=YES N=65009
77 Incorrect 62 ms 8388 KB Added cell 63774 (309,-699) not reachable from infinity
78 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5932 KB ans=NO N=66151
2 Correct 18 ms 3420 KB ans=NO N=64333
3 Incorrect 51 ms 4780 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 6180)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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