Submission #1261695

#TimeUsernameProblemLanguageResultExecution timeMemory
1261695kikitop1ggNaval battle (CEOI24_battle)C++17
0 / 100
117 ms21184 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, vi> diag; 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]; x += y; diag[x].push_back(i); } vector<pair<ll, pp>> deaths; for(auto&[d, v] : diag) { for(int i = 0; i < v.size() - 1; i++) { ll ind1 = v[i], ind2 = v[i + 1]; if(type[ind1] != 'S' || type[ind2] != 'E') continue; ll time = abs(a[ind1].first - a[ind2].first); 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 */
#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...