Submission #1134386

#TimeUsernameProblemLanguageResultExecution timeMemory
1134386aliarapovNaval battle (CEOI24_battle)C++20
36 / 100
147 ms25252 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; } template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; } template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve() { int n; cin >> n; if (n > 5000) { map<int, vector<tuple<int, bool, int> > > mp; for (int i = 0; i < n; i++) { int x, y; string dir; cin >> x >> y >> dir; mp[x + y].push_back({x, dir[0] == 'S', i + 1}); } vector<int> ans; for (auto [sum, v] : mp) { vector<int> c; sort(all(v)); for (auto [x, ty, ind] : v) { if (ty == 0) c.push_back(ind); else { if (c.empty()) ans.push_back(ind); else c.pop_back(); } } for (int i : c) ans.push_back(i); } for (int i : ans) cout << i << '\n'; } else { vector<array<int, 2> > a(n); vector<char> t(n); for (int i = 0; i < n; i++) { int x, y; char dir; cin >> x >> y >> dir; a[i] = {x, y}; t[i] = dir; } vector<array<int, 3> > v; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (t[i] == 'N' and t[j] == 'W' and a[i][0] + a[i][1] == a[j][0] + a[j][1]) v.push_back({abs(a[i][0] - a[j][0]), i, j}); if (t[i] == 'E' and t[j] == 'S' and a[i][0] + a[i][1] == a[j][0] + a[j][1]) v.push_back({abs(a[i][0] - a[j][0]), i, j}); if (t[i] == 'E' and t[j] == 'N' and a[i][0] - a[i][1] == a[j][0] - a[j][1]) v.push_back({abs(a[i][0] - a[j][0]), i, j}); if (t[i] == 'S' and t[j] == 'W' and a[i][0] - a[i][1] == a[j][0] - a[j][1]) v.push_back({abs(a[i][0] - a[j][0]), i, j}); if (t[i] == 'E' and t[j] == 'W' and a[i][1] == a[j][1]) v.push_back({abs(a[i][0] - a[j][0]), i, j}); if (t[i] == 'N' and t[j] == 'S' and a[i][0] == a[j][0]) v.push_back({abs(a[i][1] - a[j][1]), i, j}); } } sort(all(v)); vector<int> vis(n); for (auto [val, i, j] : v) { if (!vis[i] and !vis[j]) { vis[i] = val; vis[j] = val; } else if (!vis[i] and val == vis[j]) { vis[i] = val; } else if (!vis[j] and val == vis[i]) { vis[j] = val; } } vector<int> ans; for (int i = 0; i < n; i++) if (!vis[i]) ans.push_back(i); for (int i : ans) cout << i + 1 << '\n'; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int t = 1; //cin >> t; while(t--){ solve(); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...