oj.uz

Submission #598821

# Submission time Handle Problem Language Result Execution time Memory
598821 2022-07-19T06:08:29 Z 이동현(#8460) Building Skyscrapers (CEOI19_skyscrapers) C++17
34 / 100
 3500 ms 6456 KB 
#include <bits/stdc++.h>

using namespace std;

int wx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, wy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main(){
    int n, t; cin >> n >> t;
    vector<pair<int, int>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    map<int, map<int, int>> mp;
    vector<int> chk(n);
    vector<int> ans;

    for(int rep = 0; rep < n; ++rep){
        pair<int, int> now = {(int)2e9, (int)2e9};
        int pos = -1;
        for(int i = 0; i < n; ++i){
            if(chk[i]){
                continue;
            }
            int cnt = 0;
            for(int j = 0; j < 8; ++j){
                cnt += mp[a[i].first + wx[j]][a[i].second + wy[j]];
                if(cnt) break;
            }
            if(!cnt && rep) continue;
            if(a[i] < now){
                now = a[i];
                pos = i;
            }
        }
        if(now.first == (int)2e9){
            cout << "NO\n";
            return 0;
        }
        chk[pos] = 1;
        ans.push_back(pos);
        mp[a[pos].first][a[pos].second] = 1;
    }
    cout << "YES\n";
    for(auto&i:ans){
        cout << i + 1 << '\n';
    }
    return 0;
}

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 1 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 1 ms 212 KB ans=YES N=5
7 Correct 0 ms 304 KB ans=NO N=9
8 Correct 1 ms 316 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 328 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 1 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 1 ms 212 KB ans=YES N=5
7 Correct 0 ms 304 KB ans=NO N=9
8 Correct 1 ms 316 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 328 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 2 ms 212 KB ans=YES N=100
20 Correct 4 ms 212 KB ans=YES N=185
21 Correct 1 ms 340 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 4 ms 212 KB ans=YES N=183
26 Correct 5 ms 300 KB ans=YES N=188
27 Correct 5 ms 296 KB ans=YES N=183
28 Correct 4 ms 212 KB ans=YES N=189
29 Correct 5 ms 300 KB ans=YES N=200
30 Correct 5 ms 212 KB ans=YES N=190
31 Correct 5 ms 212 KB ans=YES N=187
32 Correct 5 ms 212 KB ans=YES N=187
33 Correct 5 ms 212 KB ans=YES N=182
34 Correct 7 ms 340 KB ans=YES N=184
35 Correct 6 ms 336 KB ans=YES N=188
36 Correct 5 ms 328 KB ans=YES N=181
37 Correct 6 ms 300 KB ans=YES N=188
38 Correct 7 ms 344 KB ans=YES N=191
39 Correct 5 ms 212 KB ans=YES N=196
40 Correct 6 ms 212 KB ans=YES N=196
41 Correct 5 ms 212 KB ans=YES N=196
42 Correct 5 ms 300 KB ans=YES N=196
43 Correct 6 ms 340 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 1 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 1 ms 212 KB ans=YES N=5
7 Correct 0 ms 304 KB ans=NO N=9
8 Correct 1 ms 316 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 328 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 2 ms 212 KB ans=YES N=100
20 Correct 4 ms 212 KB ans=YES N=185
21 Correct 1 ms 340 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 4 ms 212 KB ans=YES N=183
26 Correct 5 ms 300 KB ans=YES N=188
27 Correct 5 ms 296 KB ans=YES N=183
28 Correct 4 ms 212 KB ans=YES N=189
29 Correct 5 ms 300 KB ans=YES N=200
30 Correct 5 ms 212 KB ans=YES N=190
31 Correct 5 ms 212 KB ans=YES N=187
32 Correct 5 ms 212 KB ans=YES N=187
33 Correct 5 ms 212 KB ans=YES N=182
34 Correct 7 ms 340 KB ans=YES N=184
35 Correct 6 ms 336 KB ans=YES N=188
36 Correct 5 ms 328 KB ans=YES N=181
37 Correct 6 ms 300 KB ans=YES N=188
38 Correct 7 ms 344 KB ans=YES N=191
39 Correct 5 ms 212 KB ans=YES N=196
40 Correct 6 ms 212 KB ans=YES N=196
41 Correct 5 ms 212 KB ans=YES N=196
42 Correct 5 ms 300 KB ans=YES N=196
43 Correct 6 ms 340 KB ans=YES N=195
44 Correct 6 ms 1556 KB ans=NO N=1934
45 Correct 106 ms 596 KB ans=NO N=1965
46 Correct 802 ms 424 KB ans=YES N=1824
47 Correct 1006 ms 448 KB ans=YES N=1981
48 Correct 781 ms 436 KB ans=YES N=1814
49 Correct 896 ms 588 KB ans=YES N=1854
50 Correct 808 ms 460 KB ans=YES N=1831
51 Correct 998 ms 472 KB ans=YES N=2000
52 Correct 1010 ms 520 KB ans=YES N=1847
53 Correct 944 ms 668 KB ans=YES N=1819
54 Correct 1038 ms 468 KB ans=YES N=1986
55 Correct 1245 ms 624 KB ans=YES N=2000
56 Correct 1056 ms 660 KB ans=YES N=1834
57 Correct 1092 ms 632 KB ans=YES N=1860
58 Correct 1179 ms 648 KB ans=YES N=1898
59 Correct 1059 ms 584 KB ans=YES N=1832
60 Correct 1328 ms 736 KB ans=YES N=1929
61 Correct 1022 ms 500 KB ans=YES N=1919
62 Correct 1078 ms 604 KB ans=YES N=1882
63 Correct 1210 ms 776 KB ans=YES N=1922
64 Correct 1078 ms 564 KB ans=YES N=1989
65 Correct 1113 ms 564 KB ans=YES N=1978
66 Correct 911 ms 596 KB ans=YES N=1867
67 Correct 1076 ms 580 KB ans=YES N=1942

Subtask #4
0 / 17.0

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

Subtask #5
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 1 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 1 ms 212 KB ans=YES N=5
7 Correct 0 ms 304 KB ans=NO N=9
8 Correct 1 ms 316 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 328 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 2 ms 212 KB ans=YES N=100
20 Correct 4 ms 212 KB ans=YES N=185
21 Correct 1 ms 340 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 4 ms 212 KB ans=YES N=183
26 Correct 5 ms 300 KB ans=YES N=188
27 Correct 5 ms 296 KB ans=YES N=183
28 Correct 4 ms 212 KB ans=YES N=189
29 Correct 5 ms 300 KB ans=YES N=200
30 Correct 5 ms 212 KB ans=YES N=190
31 Correct 5 ms 212 KB ans=YES N=187
32 Correct 5 ms 212 KB ans=YES N=187
33 Correct 5 ms 212 KB ans=YES N=182
34 Correct 7 ms 340 KB ans=YES N=184
35 Correct 6 ms 336 KB ans=YES N=188
36 Correct 5 ms 328 KB ans=YES N=181
37 Correct 6 ms 300 KB ans=YES N=188
38 Correct 7 ms 344 KB ans=YES N=191
39 Correct 5 ms 212 KB ans=YES N=196
40 Correct 6 ms 212 KB ans=YES N=196
41 Correct 5 ms 212 KB ans=YES N=196
42 Correct 5 ms 300 KB ans=YES N=196
43 Correct 6 ms 340 KB ans=YES N=195
44 Correct 6 ms 1556 KB ans=NO N=1934
45 Correct 106 ms 596 KB ans=NO N=1965
46 Correct 802 ms 424 KB ans=YES N=1824
47 Correct 1006 ms 448 KB ans=YES N=1981
48 Correct 781 ms 436 KB ans=YES N=1814
49 Correct 896 ms 588 KB ans=YES N=1854
50 Correct 808 ms 460 KB ans=YES N=1831
51 Correct 998 ms 472 KB ans=YES N=2000
52 Correct 1010 ms 520 KB ans=YES N=1847
53 Correct 944 ms 668 KB ans=YES N=1819
54 Correct 1038 ms 468 KB ans=YES N=1986
55 Correct 1245 ms 624 KB ans=YES N=2000
56 Correct 1056 ms 660 KB ans=YES N=1834
57 Correct 1092 ms 632 KB ans=YES N=1860
58 Correct 1179 ms 648 KB ans=YES N=1898
59 Correct 1059 ms 584 KB ans=YES N=1832
60 Correct 1328 ms 736 KB ans=YES N=1929
61 Correct 1022 ms 500 KB ans=YES N=1919
62 Correct 1078 ms 604 KB ans=YES N=1882
63 Correct 1210 ms 776 KB ans=YES N=1922
64 Correct 1078 ms 564 KB ans=YES N=1989
65 Correct 1113 ms 564 KB ans=YES N=1978
66 Correct 911 ms 596 KB ans=YES N=1867
67 Correct 1076 ms 580 KB ans=YES N=1942
68 Execution timed out 3588 ms 6456 KB Time limit exceeded
69 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3536 ms 6092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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