제출 #1040981

#제출 시각아이디문제언어결과실행 시간메모리
1040981LucppNaval battle (CEOI24_battle)C++17
100 / 100
725 ms133356 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<long, long>; #define all(x) (x).begin(), (x).end() #define sz(x) (int)size(x) constexpr ll inf = 1e18; map<char, pair<int, int>> vecs = {{'N', {0, -1}}, {'E', {1, 0}}, {'S', {0, 1}}, {'W', {-1, 0}}}; int main(){ cin.tie(0)->sync_with_stdio(false); int n; cin >> n; vector<ll> x(n), y(n); vector<char> dir(n); map<ll, vector<int>> ES, EW, EN, SN, WS, WN; for(int i = 0; i < n; i++){ cin >> x[i] >> y[i] >> dir[i]; ll s = x[i], t = y[i]; if(dir[i] == 'E'){ ES[s+t].push_back(i); EW[t ].push_back(i); EN[s-t].push_back(i); } if(dir[i] == 'S'){ ES[s+t].push_back(i); SN[s ].push_back(i); WS[s-t].push_back(i); } if(dir[i] == 'W'){ WN[s+t].push_back(i); EW[t ].push_back(i); WS[s-t].push_back(i); } if(dir[i] == 'N'){ WN[s+t].push_back(i); SN[s ].push_back(i); EN[s-t].push_back(i); } } vector<list<int>> lines; vector<vector<pair<list<int>::iterator, int>>> ptr(n); priority_queue<tuple<ll, int, int>> pq; auto calcTime = [&](int i, int j){ if(dir[i] == dir[j]) return inf; auto [ivx, ivy] = vecs[dir[i]]; auto [jvx, jvy] = vecs[dir[j]]; ll vx = ivx - jvx, vy = ivy - jvy; ll dx = x[j] - x[i], dy = y[j] - y[i]; ll factor = 0; if(vx != 0) factor = dx / vx; else factor = dy / vy; assert(vx * factor == dx && vy * factor == dy); if(factor < 0) return inf; else return factor; }; auto init = [&](map<ll, vector<int>>& mp, function<ll(int)> f){ for(auto &[_, v] : mp){ sort(all(v), [&](int a, int b){return f(a) < f(b);}); lines.push_back(list<int>(all(v))); int prv = -1; for(auto it = lines.back().begin(); it != lines.back().end(); it++){ ptr[*it].emplace_back(it, sz(lines)-1); if(prv != -1) pq.emplace(-calcTime(prv, *it), prv, *it); prv = *it; } } }; init(ES, [&](int i){return x[i];}); init(EW, [&](int i){return x[i];}); init(EN, [&](int i){return x[i];}); init(SN, [&](int i){return y[i];}); init(WS, [&](int i){return x[i];}); init(WN, [&](int i){return x[i];}); vector<ll> killed(n, inf); auto remove = [&](int r){ for(auto [it, ind] : ptr[r]){ int i = -1, j = -1; if(it != lines[ind].begin()) i = *prev(it); if(next(it) != lines[ind].end()) j = *next(it); if(i != -1 && j != -1) pq.emplace(-calcTime(i, j), i, j); lines[ind].erase(it); }; }; while(!pq.empty()){ auto [t, i, j] = pq.top(); pq.pop(); t = -t; if(t == inf) break; if(killed[i] < t || killed[j] < t) continue; if(killed[i] == inf) remove(i); if(killed[j] == inf) remove(j); killed[i] = killed[j] = t; } for(int i = 0; i < n; i++){ if(killed[i] == inf) cout << (i+1) << "\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...