Submission #564578

#TimeUsernameProblemLanguageResultExecution timeMemory
564578RealSnakeBuilding Skyscrapers (CEOI19_skyscrapers)C++14
0 / 100
12 ms1464 KiB
#include "bits/stdc++.h" using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define ll long long #define mod 1000000007 ofstream fout(".out"); ifstream fin(".in"); int n, t; bool vis[11][11], viss[11][11]; int xi[8] = {0, 0, 1, -1, 1, 1, -1, -1}; int yi[8] = {-1, 1, 0, 0, -1, 1, -1, 1}; bool check(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; } bool check2(int x, int y) { vis[x][y] = 1; bool b = 0; for(int i = 0; i < 4; i++) { int xx = x + xi[i]; int yy = y + yi[i]; if(!check(xx, yy)) b = 1; else if(!vis[xx][yy]) b |= check2(xx, yy); if(b) return 1; } return 0; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> t; vector<pair<int, int>> v; for(int i = 0; i < n; i++) { int x, y; cin >> x >> y; v.push_back({x, y}); } if(n <= 10) { vector<int> vec; for(int i = 0; i < n; i++) vec.push_back(i); vector<int> ans; do { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) vis[i][j] = viss[i][j] = 0; } bool yes = 1; for(int i = 0; i < n; i++) { int j = vec[i]; int x = v[j].first, y = v[j].second; viss[x][y] = 1; for(int j = 0; j < 8; j++) { if(!i) break; int xx = x + xi[j]; int yy = y + yi[j]; if(check(xx, yy) && viss[xx][yy]) break; if(j == 7) { yes = 0; break; } } if(!yes || !check2(x, y)) { yes = 0; break; } } if(yes) { if(!ans.size()) ans = vec; else if(vec > ans) ans = vec; } } while(next_permutation(vec.begin(), vec.end())); if(ans.size()) { cout << "YES\n"; reverse(ans.begin(), ans.end()); for(int i : ans) cout << i + 1 << "\n"; } else cout << "NO\n"; } return 0; }
#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...