oj.uz

Submission #943974

# Submission time Handle Problem Language Result Execution time Memory
943974 2024-03-12T05:55:46 Z vjudge1 Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 317 ms 75192 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}

const vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
const vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, t; cin >> n >> t;
  int x[n], y[n];
  map<int, map<int, bool>> vis;
  map<int, map<int, int>> used;
  int Min = -1;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
    used[x[i]][y[i]] = i + 1;
    if (Min == -1 || x[Min] + y[Min] > x[i]) {
      Min = i;
    }
  }
  vector<int> res;
  priority_queue<array<int, 3>, 
    vector<array<int, 3>>,
    greater<array<int, 3>>> q;
  q.push({x[Min] + y[Min], x[Min], Min});
  vis[x[Min]][y[Min]] = true;
  while (!q.empty()) {
    int i = q.top()[2];
    res.push_back(i + 1);
    q.pop();
    for (int j = 0; j < 8; ++j) {
      int to_x = x[i] + dx[j], to_y = y[i] + dy[j];
      if (used[to_x][to_y]) {
        if (!vis[to_x][to_y]) {
          vis[to_x][to_y] = true;
          q.push({to_x, to_y, used[to_x][to_y] - 1});
        }
      }
    }
  }
  if (size(res) < n) {
    cout << "NO";
    return 0;
  }
  cout << "YES\n";
  for (auto i : res) cout << i << '\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 17.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 1 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 1 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 512 KB ans=NO N=10
9 Correct 1 ms 348 KB ans=YES N=10
10 Correct 0 ms 348 KB ans=YES N=10
11 Correct 1 ms 348 KB ans=YES N=10
12 Correct 1 ms 348 KB ans=YES N=9
13 Correct 1 ms 348 KB ans=YES N=9
14 Correct 1 ms 348 KB ans=YES N=8
15 Correct 0 ms 348 KB ans=YES N=8
16 Correct 1 ms 348 KB ans=NO N=2
17 Correct 1 ms 348 KB ans=YES N=17
18 Correct 1 ms 348 KB ans=YES N=25
19 Correct 1 ms 348 KB ans=YES N=100
20 Correct 1 ms 348 KB ans=YES N=185
21 Correct 0 ms 348 KB ans=NO N=174
22 Correct 1 ms 344 KB ans=YES N=90
23 Correct 1 ms 348 KB ans=YES N=63
24 Correct 1 ms 348 KB ans=YES N=87
25 Correct 1 ms 600 KB ans=YES N=183
26 Correct 1 ms 348 KB ans=YES N=188
27 Correct 1 ms 348 KB ans=YES N=183
28 Correct 1 ms 348 KB ans=YES N=189
29 Correct 1 ms 348 KB ans=YES N=200
30 Correct 1 ms 348 KB ans=YES N=190
31 Correct 1 ms 348 KB ans=YES N=187
32 Correct 0 ms 348 KB ans=YES N=187
33 Correct 1 ms 348 KB ans=YES N=182
34 Correct 1 ms 348 KB ans=YES N=184
35 Correct 1 ms 352 KB ans=YES N=188
36 Correct 1 ms 356 KB ans=YES N=181
37 Correct 1 ms 360 KB ans=YES N=188
38 Correct 1 ms 356 KB ans=YES N=191
39 Correct 1 ms 344 KB ans=YES N=196
40 Correct 1 ms 352 KB ans=YES N=196
41 Correct 1 ms 360 KB ans=YES N=196
42 Correct 1 ms 356 KB ans=YES N=196
43 Correct 1 ms 356 KB ans=YES N=195
44 Correct 1 ms 604 KB ans=NO N=1934
45 Correct 1 ms 604 KB ans=NO N=1965
46 Correct 4 ms 608 KB ans=YES N=1824
47 Correct 3 ms 604 KB ans=YES N=1981
48 Correct 3 ms 604 KB ans=YES N=1814
49 Correct 3 ms 724 KB ans=YES N=1854
50 Correct 3 ms 604 KB ans=YES N=1831
51 Correct 3 ms 604 KB ans=YES N=2000
52 Correct 3 ms 604 KB ans=YES N=1847
53 Correct 3 ms 860 KB ans=YES N=1819
54 Correct 3 ms 604 KB ans=YES N=1986
55 Correct 3 ms 860 KB ans=YES N=2000
56 Correct 3 ms 860 KB ans=YES N=1834
57 Correct 3 ms 860 KB ans=YES N=1860
58 Correct 3 ms 860 KB ans=YES N=1898
59 Correct 3 ms 860 KB ans=YES N=1832
60 Correct 3 ms 1116 KB ans=YES N=1929
61 Correct 4 ms 600 KB ans=YES N=1919
62 Correct 3 ms 856 KB ans=YES N=1882
63 Correct 3 ms 1116 KB ans=YES N=1922
64 Correct 3 ms 860 KB ans=YES N=1989
65 Correct 3 ms 860 KB ans=YES N=1978
66 Correct 3 ms 1116 KB ans=YES N=1867
67 Correct 3 ms 860 KB ans=YES N=1942
68 Correct 111 ms 13000 KB ans=NO N=66151
69 Correct 24 ms 5536 KB ans=NO N=64333
70 Correct 101 ms 11352 KB ans=YES N=69316
71 Correct 107 ms 10956 KB ans=YES N=66695
72 Correct 106 ms 11092 KB ans=YES N=68436
73 Correct 108 ms 11504 KB ans=YES N=70000
74 Correct 103 ms 11368 KB ans=YES N=68501
75 Correct 118 ms 11760 KB ans=YES N=70000
76 Correct 99 ms 11720 KB ans=YES N=65009
77 Correct 108 ms 16484 KB ans=YES N=67007
78 Correct 118 ms 18548 KB ans=YES N=66357
79 Correct 148 ms 20008 KB ans=YES N=65430
80 Correct 133 ms 19288 KB ans=YES N=65790
81 Correct 122 ms 18212 KB ans=YES N=66020
82 Correct 112 ms 17200 KB ans=YES N=65809
83 Correct 102 ms 13128 KB ans=YES N=65651
84 Correct 139 ms 23624 KB ans=YES N=68040
85 Correct 116 ms 21440 KB ans=YES N=66570
86 Correct 101 ms 11336 KB ans=YES N=65421
87 Correct 109 ms 12508 KB ans=YES N=68351
88 Correct 100 ms 10956 KB ans=YES N=67027
89 Correct 89 ms 15300 KB ans=YES N=68879
90 Correct 102 ms 12492 KB ans=YES N=67256
91 Correct 265 ms 24220 KB ans=YES N=148315
92 Correct 58 ms 11604 KB ans=NO N=142745
93 Correct 135 ms 25936 KB ans=NO N=148443
94 Correct 275 ms 23784 KB ans=YES N=148328
95 Correct 249 ms 23740 KB ans=YES N=147855
96 Correct 310 ms 23940 KB ans=YES N=150000
97 Correct 275 ms 23120 KB ans=YES N=144725
98 Correct 316 ms 23744 KB ans=YES N=149445
99 Correct 245 ms 23264 KB ans=YES N=144455
100 Correct 247 ms 23232 KB ans=YES N=143487
101 Correct 252 ms 24164 KB ans=YES N=149688
102 Correct 276 ms 35188 KB ans=YES N=141481
103 Correct 317 ms 49400 KB ans=YES N=147430
104 Correct 262 ms 29748 KB ans=YES N=142247
105 Correct 291 ms 34496 KB ans=YES N=149941
106 Correct 287 ms 48076 KB ans=YES N=141635
107 Correct 306 ms 41284 KB ans=YES N=142896
108 Correct 290 ms 44984 KB ans=YES N=142069
109 Correct 254 ms 25808 KB ans=YES N=142378
110 Correct 273 ms 39616 KB ans=YES N=150000
111 Correct 287 ms 52416 KB ans=YES N=141452
112 Correct 288 ms 55000 KB ans=YES N=134453
113 Correct 315 ms 75192 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 13188 KB ans=NO N=66151
2 Correct 24 ms 5468 KB ans=NO N=64333
3 Incorrect 124 ms 11196 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 1 ms 600 KB ans=NO N=1934
2 Correct 2 ms 848 KB ans=NO N=1965
3 Incorrect 3 ms 604 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -