oj.uz

Submission #476138

# Submission time Handle Problem Language Result Execution time Memory
476138 2021-09-25T00:04:52 Z Ozy Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 217 ms 15648 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 150000

lli n,t,a,b,ini,val,act,k;
map<pair<lli,lli>, lli> mapa;
vector<lli> hijos[MAX+2];
lli dir[16] = {-1,0,1,0,-1,1,1,-1,0,1,0,-1,1,1,-1,-1};
lli visitados[MAX+2];
queue<lli> cola;
vector<lli> res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> t;

    val = 1000000000000;
    rep(i,1,n) {
        cin >> a >> b;
        if (a < val){
            val = a;
            ini = i;
        }

        mapa[{a,b}] = i;

        rep(o,0,7) {
            if (mapa.find({a+dir[o],b + dir[o+8]}) != mapa.end()) {
                k = mapa[{a+dir[o],b + dir[o+8]}];
                hijos[k].push_back(i);
                hijos[i].push_back(k);
            }
        }
    }
    //correcto

    cola.push(ini);
    visitados[ini] = 1;
    while (!cola.empty()) {

        act = cola.front();
        cola.pop();
        res.push_back(act);

        for(auto h : hijos[act]) {
            if (visitados[h] == 1) continue;
            visitados[h] = 1;
            cola.push(h);
        }
    }

    if (res.size() < n) cout << "NO";
    else {
        cout << "YES\n";
        for (auto r : res) cout << r << "\n";
    }
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:62:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   62 |     if (res.size() < n) cout << "NO";
      |         ~~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3788 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 2 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 3 ms 3788 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3788 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2
17 Correct 2 ms 3788 KB ans=YES N=17
18 Correct 2 ms 3788 KB ans=YES N=25
19 Correct 2 ms 3788 KB ans=YES N=100
20 Correct 3 ms 3788 KB ans=YES N=185
21 Correct 2 ms 3788 KB ans=NO N=174
22 Correct 2 ms 3788 KB ans=YES N=90
23 Correct 2 ms 3788 KB ans=YES N=63
24 Correct 2 ms 3788 KB ans=YES N=87
25 Correct 2 ms 3788 KB ans=YES N=183
26 Correct 2 ms 3788 KB ans=YES N=188
27 Correct 3 ms 3788 KB ans=YES N=183
28 Correct 3 ms 3788 KB ans=YES N=189
29 Correct 2 ms 3788 KB ans=YES N=200
30 Correct 2 ms 3788 KB ans=YES N=190
31 Correct 2 ms 3788 KB ans=YES N=187
32 Correct 3 ms 3864 KB ans=YES N=187
33 Correct 2 ms 3788 KB ans=YES N=182
34 Correct 2 ms 3788 KB ans=YES N=184
35 Correct 2 ms 3788 KB ans=YES N=188
36 Correct 2 ms 3788 KB ans=YES N=181
37 Correct 2 ms 3788 KB ans=YES N=188
38 Correct 2 ms 3788 KB ans=YES N=191
39 Incorrect 2 ms 3788 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3788 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 2 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 3 ms 3788 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3788 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2
17 Correct 2 ms 3788 KB ans=YES N=17
18 Correct 2 ms 3788 KB ans=YES N=25
19 Correct 2 ms 3788 KB ans=YES N=100
20 Correct 3 ms 3788 KB ans=YES N=185
21 Correct 2 ms 3788 KB ans=NO N=174
22 Correct 2 ms 3788 KB ans=YES N=90
23 Correct 2 ms 3788 KB ans=YES N=63
24 Correct 2 ms 3788 KB ans=YES N=87
25 Correct 2 ms 3788 KB ans=YES N=183
26 Correct 2 ms 3788 KB ans=YES N=188
27 Correct 3 ms 3788 KB ans=YES N=183
28 Correct 3 ms 3788 KB ans=YES N=189
29 Correct 2 ms 3788 KB ans=YES N=200
30 Correct 2 ms 3788 KB ans=YES N=190
31 Correct 2 ms 3788 KB ans=YES N=187
32 Correct 3 ms 3864 KB ans=YES N=187
33 Correct 2 ms 3788 KB ans=YES N=182
34 Correct 2 ms 3788 KB ans=YES N=184
35 Correct 2 ms 3788 KB ans=YES N=188
36 Correct 2 ms 3788 KB ans=YES N=181
37 Correct 2 ms 3788 KB ans=YES N=188
38 Correct 2 ms 3788 KB ans=YES N=191
39 Incorrect 2 ms 3788 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3892 KB ans=NO N=1934
2 Correct 4 ms 4044 KB ans=NO N=1965
3 Incorrect 5 ms 4044 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 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3788 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 2 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 3 ms 3788 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3788 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2
17 Correct 2 ms 3788 KB ans=YES N=17
18 Correct 2 ms 3788 KB ans=YES N=25
19 Correct 2 ms 3788 KB ans=YES N=100
20 Correct 3 ms 3788 KB ans=YES N=185
21 Correct 2 ms 3788 KB ans=NO N=174
22 Correct 2 ms 3788 KB ans=YES N=90
23 Correct 2 ms 3788 KB ans=YES N=63
24 Correct 2 ms 3788 KB ans=YES N=87
25 Correct 2 ms 3788 KB ans=YES N=183
26 Correct 2 ms 3788 KB ans=YES N=188
27 Correct 3 ms 3788 KB ans=YES N=183
28 Correct 3 ms 3788 KB ans=YES N=189
29 Correct 2 ms 3788 KB ans=YES N=200
30 Correct 2 ms 3788 KB ans=YES N=190
31 Correct 2 ms 3788 KB ans=YES N=187
32 Correct 3 ms 3864 KB ans=YES N=187
33 Correct 2 ms 3788 KB ans=YES N=182
34 Correct 2 ms 3788 KB ans=YES N=184
35 Correct 2 ms 3788 KB ans=YES N=188
36 Correct 2 ms 3788 KB ans=YES N=181
37 Correct 2 ms 3788 KB ans=YES N=188
38 Correct 2 ms 3788 KB ans=YES N=191
39 Incorrect 2 ms 3788 KB Added cell 196 (16,2) not reachable from infinity
40 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 14488 KB ans=NO N=66151
2 Correct 133 ms 8664 KB ans=NO N=64333
3 Incorrect 217 ms 15648 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 13970)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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