oj.uz

Submission #533203

# Submission time Handle Problem Language Result Execution time Memory
533203 2022-03-05T06:28:13 Z wenqi Building Skyscrapers (CEOI19_skyscrapers) C++17
22 / 100
 72 ms 6032 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({-max(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 1 ms 204 KB ans=YES N=1
2 Correct 1 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 1 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 1 ms 204 KB ans=NO N=9
8 Correct 1 ms 204 KB ans=NO N=10
9 Correct 1 ms 204 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 1 ms 204 KB ans=YES N=8
16 Correct 1 ms 204 KB ans=NO N=2

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ans=YES N=1
2 Correct 1 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 1 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 1 ms 204 KB ans=NO N=9
8 Correct 1 ms 204 KB ans=NO N=10
9 Correct 1 ms 204 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 1 ms 204 KB ans=YES N=8
16 Correct 1 ms 204 KB ans=NO N=2
17 Correct 1 ms 204 KB ans=YES N=17
18 Correct 1 ms 204 KB ans=YES N=25
19 Correct 1 ms 332 KB ans=YES N=100
20 Correct 1 ms 320 KB ans=YES N=185
21 Correct 1 ms 332 KB ans=NO N=174
22 Correct 0 ms 332 KB ans=YES N=90
23 Correct 1 ms 332 KB ans=YES N=63
24 Correct 1 ms 316 KB ans=YES N=87
25 Correct 1 ms 332 KB ans=YES N=183
26 Correct 1 ms 332 KB ans=YES N=188
27 Correct 1 ms 332 KB ans=YES N=183
28 Correct 1 ms 332 KB ans=YES N=189
29 Correct 1 ms 332 KB ans=YES N=200
30 Correct 1 ms 332 KB ans=YES N=190
31 Correct 1 ms 332 KB ans=YES N=187
32 Correct 1 ms 332 KB ans=YES N=187
33 Correct 1 ms 332 KB ans=YES N=182
34 Correct 1 ms 332 KB ans=YES N=184
35 Correct 1 ms 332 KB ans=YES N=188
36 Correct 1 ms 332 KB ans=YES N=181
37 Correct 1 ms 332 KB ans=YES N=188
38 Correct 1 ms 332 KB ans=YES N=191
39 Correct 1 ms 332 KB ans=YES N=196
40 Correct 1 ms 332 KB ans=YES N=196
41 Correct 1 ms 332 KB ans=YES N=196
42 Correct 1 ms 332 KB ans=YES N=196
43 Correct 1 ms 332 KB ans=YES N=195
44 Correct 1 ms 460 KB ans=NO N=1934
45 Correct 1 ms 332 KB ans=NO N=1965
46 Correct 2 ms 460 KB ans=YES N=1824
47 Correct 3 ms 460 KB ans=YES N=1981
48 Correct 2 ms 460 KB ans=YES N=1814
49 Correct 3 ms 468 KB ans=YES N=1854
50 Correct 3 ms 460 KB ans=YES N=1831
51 Correct 3 ms 460 KB ans=YES N=2000
52 Correct 3 ms 460 KB ans=YES N=1847
53 Correct 2 ms 460 KB ans=YES N=1819
54 Correct 3 ms 460 KB ans=YES N=1986
55 Correct 3 ms 588 KB ans=YES N=2000
56 Correct 4 ms 592 KB ans=YES N=1834
57 Correct 3 ms 684 KB ans=YES N=1860
58 Correct 3 ms 588 KB ans=YES N=1898
59 Incorrect 2 ms 588 KB Added cell 1651 (-114292865,-624435398) not reachable from infinity
60 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ans=YES N=1
2 Correct 1 ms 204 KB ans=YES N=4
3 Correct 0 ms 204 KB ans=NO N=4
4 Correct 1 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 1 ms 204 KB ans=NO N=9
8 Correct 1 ms 204 KB ans=NO N=10
9 Correct 1 ms 204 KB ans=YES N=10
10 Correct 1 ms 204 KB ans=YES N=10
11 Correct 1 ms 204 KB ans=YES N=10
12 Correct 1 ms 204 KB ans=YES N=9
13 Correct 1 ms 204 KB ans=YES N=9
14 Correct 1 ms 204 KB ans=YES N=8
15 Correct 1 ms 204 KB ans=YES N=8
16 Correct 1 ms 204 KB ans=NO N=2
17 Correct 1 ms 204 KB ans=YES N=17
18 Correct 1 ms 204 KB ans=YES N=25
19 Correct 1 ms 332 KB ans=YES N=100
20 Correct 1 ms 320 KB ans=YES N=185
21 Correct 1 ms 332 KB ans=NO N=174
22 Correct 0 ms 332 KB ans=YES N=90
23 Correct 1 ms 332 KB ans=YES N=63
24 Correct 1 ms 316 KB ans=YES N=87
25 Correct 1 ms 332 KB ans=YES N=183
26 Correct 1 ms 332 KB ans=YES N=188
27 Correct 1 ms 332 KB ans=YES N=183
28 Correct 1 ms 332 KB ans=YES N=189
29 Correct 1 ms 332 KB ans=YES N=200
30 Correct 1 ms 332 KB ans=YES N=190
31 Correct 1 ms 332 KB ans=YES N=187
32 Correct 1 ms 332 KB ans=YES N=187
33 Correct 1 ms 332 KB ans=YES N=182
34 Correct 1 ms 332 KB ans=YES N=184
35 Correct 1 ms 332 KB ans=YES N=188
36 Correct 1 ms 332 KB ans=YES N=181
37 Correct 1 ms 332 KB ans=YES N=188
38 Correct 1 ms 332 KB ans=YES N=191
39 Correct 1 ms 332 KB ans=YES N=196
40 Correct 1 ms 332 KB ans=YES N=196
41 Correct 1 ms 332 KB ans=YES N=196
42 Correct 1 ms 332 KB ans=YES N=196
43 Correct 1 ms 332 KB ans=YES N=195
44 Correct 1 ms 460 KB ans=NO N=1934
45 Correct 1 ms 332 KB ans=NO N=1965
46 Correct 2 ms 460 KB ans=YES N=1824
47 Correct 3 ms 460 KB ans=YES N=1981
48 Correct 2 ms 460 KB ans=YES N=1814
49 Correct 3 ms 468 KB ans=YES N=1854
50 Correct 3 ms 460 KB ans=YES N=1831
51 Correct 3 ms 460 KB ans=YES N=2000
52 Correct 3 ms 460 KB ans=YES N=1847
53 Correct 2 ms 460 KB ans=YES N=1819
54 Correct 3 ms 460 KB ans=YES N=1986
55 Correct 3 ms 588 KB ans=YES N=2000
56 Correct 4 ms 592 KB ans=YES N=1834
57 Correct 3 ms 684 KB ans=YES N=1860
58 Correct 3 ms 588 KB ans=YES N=1898
59 Incorrect 2 ms 588 KB Added cell 1651 (-114292865,-624435398) not reachable from infinity
60 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6032 KB ans=NO N=66151
2 Correct 19 ms 3544 KB ans=NO N=64333
3 Incorrect 72 ms 5012 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 7320)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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