Submission #810958

#TimeUsernameProblemLanguageResultExecution timeMemory
810958treewaveBuilding Skyscrapers (CEOI19_skyscrapers)C++17
8 / 100
134 ms12920 KiB
#include <bits/stdc++.h> using namespace std; int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1}; int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1}; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, t; cin >> n >> t; vector<array<int, 2>> points; set<int> points_set; map<array<int, 2>, int> pt_to_idx; for (int i = 0; i < n; i++){ int x, y; cin >> x >> y; points.push_back({x, y}); points_set.insert(i); pt_to_idx[{x, y}] = i; } queue<int> bfs; bfs.push(pt_to_idx.begin()->second); set<array<int, 2>> visited; visited.insert({points[bfs.front()][0], points[bfs.front()][1]}); vector<int> ans; while (!bfs.empty()){ int tp = bfs.front(); bfs.pop(); ans.push_back(tp); for (int d = 0; d < 8; d++){ array<int, 2> new_pt = {points[tp][0] + dx[d], points[tp][1] + dy[d]}; if (!visited.count(new_pt)){ if (pt_to_idx.count(new_pt)){ visited.insert(new_pt); bfs.push(pt_to_idx[new_pt]); } } } } if (ans.size() != n){ cout << "NO\n"; return 0; } cout << "YES\n"; for (int i = 0; i < n; i++){ cout << ans[i] + 1 << "\n"; } // if (ans.size() == n){ // cerr << "hi\n"; // set<array<int, 2>> curr_cells; // for (int i = 0; i < n; i++){ // array<int, 2> cp = points[ans[i]]; // assert(!curr_cells.count({cp[0], cp[1]+1}) || !curr_cells.count({cp[0], cp[1]-1}) || !curr_cells.count({cp[0]+1, cp[1]}) || !curr_cells.count({cp[0]-1, cp[1]})); // curr_cells.insert(cp); // } // } }

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:40:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (ans.size() != n){
      |         ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...