Submission #1208332

#TimeUsernameProblemLanguageResultExecution timeMemory
1208332HappyCapybaraNaval battle (CEOI24_battle)C++20
67 / 100
2489 ms185380 KiB
#include<bits/stdc++.h> using namespace std; #define int long long pair<int,int> bruh = {1<<30, 1<<30}; unordered_map<char,unordered_map<int,set<pair<int,int>>>> rows, cols, ru, rd; pair<int,int> gt(set<pair<int,int>>& s, int x){ auto it = s.upper_bound({x, -1}); if (it == s.end()) return bruh; return *it; } pair<int,int> lt(set<pair<int,int>>& s, int x){ auto it = s.upper_bound({x, -1}); if (it == s.begin()) return bruh; it--; return *it; } pair<int,int> find_next(int x, int y, char d){ pair<int,int> res = bruh; if (d == 'N'){ pair<int,int> pi = lt(cols['S'][x], y); if (pi != bruh) res = min(res, {abs(pi.first-y)/2, pi.second}); pi = gt(ru['W'][x+y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); pi = lt(rd['E'][x-y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); } if (d == 'S'){ pair<int,int> pi = gt(cols['N'][x], y); if (pi != bruh) res = min(res, {abs(pi.first-y)/2, pi.second}); pi = lt(ru['E'][x+y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); pi = gt(rd['W'][x-y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); } if (d == 'E'){ pair<int,int> pi = gt(rows['W'][y], x); if (pi != bruh) res = min(res, {abs(pi.first-x)/2, pi.second}); pi = gt(ru['S'][x+y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); pi = gt(rd['N'][x-y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); } if (d == 'W'){ pair<int,int> pi = lt(rows['E'][y], x); if (pi != bruh) res = min(res, {abs(pi.first-x)/2, pi.second}); pi = lt(ru['N'][x+y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); pi = lt(rd['S'][x-y], x); if (pi != bruh) res = min(res, {abs(pi.first-x), pi.second}); } return res; } signed main(){ cin.tie(0); iostream::sync_with_stdio(false); int n; cin >> n; vector<int> x(n), y(n); vector<char> d(n); for (int i=0; i<n; i++){ cin >> x[i] >> y[i] >> d[i]; rows[d[i]][y[i]].insert({x[i], i}); cols[d[i]][x[i]].insert({y[i], i}); ru[d[i]][x[i]+y[i]].insert({x[i], i}); rd[d[i]][x[i]-y[i]].insert({x[i], i}); } set<pair<int,pair<int,int>>> nc; for (int i=0; i<n; i++){ pair<int,int> next = find_next(x[i], y[i], d[i]); //cout << next.first << " " << next.second << endl; if (next != bruh) nc.insert({next.first, {i, next.second}}); } vector<bool> alive(n, true); vector<int> tod(n); while (!nc.empty()){ pair<int,pair<int,int>> cur = *nc.begin(); nc.erase(nc.begin()); int a = cur.second.first, b = cur.second.second; //cout << a << " " << b << endl; if (alive[a] && alive[b]){ alive[a] = false; tod[a] = cur.first; rows[d[a]][y[a]].erase({x[a], a}); cols[d[a]][x[a]].erase({y[a], a}); ru[d[a]][x[a]+y[a]].erase({x[a], a}); rd[d[a]][x[a]-y[a]].erase({x[a], a}); alive[b] = false; tod[b] = cur.first; rows[d[b]][y[b]].erase({x[b], b}); cols[d[b]][x[b]].erase({y[b], b}); ru[d[b]][x[b]+y[b]].erase({x[b], b}); rd[d[b]][x[b]-y[b]].erase({x[b], b}); } if (alive[a] && !alive[b]){ if (tod[b] == cur.first){ alive[a] = false; tod[a] = cur.first; rows[d[a]][y[a]].erase({x[a], a}); cols[d[a]][x[a]].erase({y[a], a}); ru[d[a]][x[a]+y[a]].erase({x[a], a}); rd[d[a]][x[a]-y[a]].erase({x[a], a}); continue; } pair<int,int> next = find_next(x[a], y[a], d[a]); if (next != bruh){ nc.insert({next.first, {a, next.second}}); //assert(alive[next.second]); //assert(next.first >= cur.first); } } if (alive[b] && !alive[a]){ if (tod[a] == cur.first){ alive[b] = false; tod[b] = cur.first; rows[d[b]][y[b]].erase({x[b], b}); cols[d[b]][x[b]].erase({y[b], b}); ru[d[b]][x[b]+y[b]].erase({x[b], b}); rd[d[b]][x[b]-y[b]].erase({x[b], b}); continue; } pair<int,int> next = find_next(x[b], y[b], d[b]); if (next != bruh){ nc.insert({next.first, {b, next.second}}); //assert(alive[next.second]); //assert(next.first >= cur.first); } } } for (int i=0; i<n; i++){ if (alive[i]) cout << i+1 << endl; } }
#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...