Submission #564682

#TimeUsernameProblemLanguageResultExecution timeMemory
564682AbdullahMWBuilding Skyscrapers (CEOI19_skyscrapers)C++14
0 / 100
3580 ms1876 KiB
#include <bits/stdc++.h> #define all(vec) vec.begin(), vec.end() #define ll long long #define db double #define pb push_back #define pf push_front #define newl "\n" #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define f first #define s second #define MOD 1000000007 using namespace std; #pragma GCC diagnostic ignored "-Wunused-result" void setIO(string name = "") { ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(15); if (name.size()) { freopen((name+".in").c_str(), "r", stdin); freopen((name+".out").c_str(), "w", stdout); } } map <pair <ll, ll>, bool> occ; unordered_map <ll, unordered_map <ll, bool>> vis; unordered_map <ll, vector <ll>> fx, fy; bool C(ll x, ll y) { if (occ[{x + 1, y}]) return 1; else if (occ[{x - 1, y}]) return 1; else if (occ[{x, y + 1}]) return 1; else if (occ[{x, y - 1}]) return 1; if (occ[{x + 1, y + 1}]) return 1; else if (occ[{x + 1, y - 1}]) return 1; else if (occ[{x - 1, y + 1}]) return 1; else if (occ[{x - 1, y - 1}]) return 1; return 0; } bool cyc; void dfs(ll px, ll py, ll x, ll y) { if (occ[{x + 1, y}]) { if (!vis[x + 1][y]) { vis[x + 1][y] = true; dfs(x, y, x + 1, y); } else cyc = true; } if (occ[{x - 1, y}]) { if (!vis[x - 1][y]) { vis[x - 1][y] = true; dfs(x, y, x - 1, y); } else cyc = true; } if (occ[{x, y + 1}]) { if (!vis[x][y + 1]) { vis[x][y + 1] = true; dfs(x, y, x, y + 1); } else cyc = true; } if (occ[{x, y - 1}]) { if (!vis[x][y - 1]) { vis[x][y - 1] = true; dfs(x, y, x, y - 1); } else cyc = true; } } int main() { fast //setIO(""); //freopen("filename.in", "r", stdin); //freopen("filename.out", "w", stdout); ll n, t; cin >> n >> t; vector <pair <ll, ll>> vec(n); vector <ll> per(n); for (ll i = 0; i < n; i++) { cin >> vec[i].f >> vec[i].s; per[i] = i; } if (n == 1) { cout << "YES" << newl << 1; return 0; } do { if (occ.size()) occ.clear(); if (vis.size()) vis.clear(); if (fx.size()) fx.clear(); if (fy.size()) fy.clear(); cyc = 0; bool works = true; ll c = 0; for (auto idx : per) { ll x = vec[idx].f, y = vec[idx].s; c++; occ[vec[idx]] = true; fx[x].pb(y); fy[y].pb(x); if (!C(x, y) && c != 1) { works = false; break; } ll yy = upper_bound(all(fx[x]), y) - fx[x].begin(); ll xx = upper_bound(all(fy[y]), x) - fy[y].begin(); if (yy != fx[x].size()) { vis[x][fx[x][yy]] = true; dfs(x, fx[x][yy], x, fx[x][yy]); } else if (xx != fy[y].size()) { vis[fy[y][xx]][x] = true; dfs(fy[y][xx], y, fy[y][xx], y); } if (cyc) { works = false; break; } } if (works) { cout << "YES" << newl; for (auto v : per) cout << v + 1 << newl; return 0; } } while(next_permutation(all(per))); cout << "NO"; }

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:141:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             if (yy != fx[x].size())
      |                 ~~~^~~~~~~~~~~~~~~
skyscrapers.cpp:146:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             else if (xx != fy[y].size())
      |                      ~~~^~~~~~~~~~~~~~~
#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...