Submission #1261709

#TimeUsernameProblemLanguageResultExecution timeMemory
1261709kikitop1ggNaval battle (CEOI24_battle)C++17
30 / 100
622 ms84892 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<ll> #define vvi vector<vector<ll>> #define vs vector<string> #define vc vector<char> #define vb vector<bool> #define vp vector<pair<ll, ll>> #define vpp vector<pair<ll, pair<ll, ll>>> #define pp pair<ll, ll> #define qi queue<ll> #define qp queue<pp> #define pqi priority_queue<ll> #define pqp priority_queue<pp> #define mi map<ll, ll> #define mpi map<pp, ll> #define mip map<ll, pp> #define mp map<pp, pp> #define mb map<ll, bool> #define si set<ll> #define sp set<pp> #define sc set<char> #define mod 1000000007 #define inf INT_MAX #define all(x) (x).begin(), (x).end() int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n; cin >> n; vp a(n); vc type(n); vector<pair<pp, ll>> north, south, east, west; map<ll, vp> diagES; map<ll, vp> diagWN; map<ll, vp> diagEN; map<ll, vp> diagWS; map<ll, vp> vert; map<ll, vp> hor; for(int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second >> type[i]; if(type[i] == 'N') { north.push_back({a[i], i}); } else if(type[i] == 'S') { south.push_back({a[i], i}); } else if(type[i] == 'W') { west.push_back({a[i], i}); } else { east.push_back({a[i], i}); } auto[x, y] = a[i]; ll d = x + y; if(type[i] == 'E' || type[i] == 'S') { diagES[d].push_back({y, i}); } else { diagWN[d].push_back({y, i}); } d = x - y; if(type[i] == 'E' || type[i] == 'N') { diagEN[d].push_back({y, i}); } else { diagWS[d].push_back({y, i}); } if(type[i] == 'W' || type[i] == 'E') { hor[y].push_back({x, i}); } else { vert[x].push_back({y, i}); } } vector<pair<ll, pp>> deaths; for(auto&[d, v] : diagES) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'S') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].first - a[ind2].first); deaths.push_back({time, {ind1, ind2}}); } } for(auto&[d, v] : diagWN) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'W') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].first - a[ind2].first); deaths.push_back({time, {ind1, ind2}}); } } for(auto&[d, v] : diagEN) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'E') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].first - a[ind2].first); deaths.push_back({time, {ind1, ind2}}); } } for(auto&[d, v] : diagWS) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'W') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].first - a[ind2].first); deaths.push_back({time, {ind1, ind2}}); } } for(auto&[d, v] : vert) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'S') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].second - a[ind2].second) / 2; deaths.push_back({time, {ind1, ind2}}); } } for(auto&[d, v] : hor) { sort(all(v)); stack<ll> st; for(int i = 0; i < v.size(); i++) { ll ind1 = v[i].second; if(type[ind1] == 'E') { st.push(ind1); continue; } if(st.size() == 0) continue; ll ind2 = st.top(); st.pop(); ll time = abs(a[ind1].first - a[ind2].first) / 2; deaths.push_back({time, {ind1, ind2}}); } } sort(all(deaths)); si left; for(int i = 0; i < n; i++) left.insert(i); for(int i = 0; i < deaths.size();) { ll curTime = deaths[i].first; si del; while(i < deaths.size() && deaths[i].first == curTime) { ll ind1 = deaths[i].second.first, ind2 = deaths[i].second.second; if(!left.count(ind1) || !left.count(ind2)) { i++; continue; } del.insert(ind1); del.insert(ind2); i++; } for(auto x : del) left.erase(x); } for(auto x : left) cout << x + 1 << '\n'; return 0; } /* 3 4 0 S 2 2 E 0 4 E 5 2 2 E 4 0 S 0 4 E 1 3 S 3 1 S 2 4 0 6 E 2 4 E 4 2 S 6 0 S 2 0 0 E 2 2 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...
#Verdict Execution timeMemoryGrader output
Fetching results...