Submission #1227178

#TimeUsernameProblemLanguageResultExecution timeMemory
1227178pravcoderNaval battle (CEOI24_battle)C++20
6 / 100
3101 ms793004 KiB
#include <bits/stdc++.h> #include <iostream> #include <queue> #include <set> using namespace std; #define pb push_back #define mp make_pair #define rept(i, a, b) for (int i = a; i < b; i++) #define rep(i, n) for (int i = 0; i < n; i++) #define vec vector #define all(x) (x).begin(), (x).end() typedef long long ll; typedef vec<int> vi; typedef vec<vi> v2i; typedef pair<ll, ll> pl; typedef pair<int, int> pi; typedef vec<pl> vpl; typedef vec<pi> vpi; typedef vec<bool> vb; typedef priority_queue<pair<int, pi>> qpi; typedef priority_queue<int> qi; //sub 1-5 ll ct(pl c1, pl c2, pi d1, pi d2) { if (d1==d2) return 0; pi rel = {d1.first - d2.first, d1.second - d2.second}; //cout << "calculating collide time" << endl; ll t = max(abs(c2.first - c1.first), abs(c2.second - c1.second)) / max(abs(rel.first), abs(rel.second)); //cout << "t = " << t << endl; if (c1.first + t*rel.first == c2.first && c1.second + t*rel.second == c2.second) return max(t, (ll)0); return 0; } void sub1(int n, vpl& c, vpi& d) { if (ct(c[0], c[1], d[0], d[1]) == 0) { cout << "1 2 \n"; } } void sub5(int n, vpl& c, vpi& d) { qpi q; rep(i, n-1) { rept(j, i+1, n) { int t = ct(c[i], c[j], d[i], d[j]); if (t!=0) { q.push({-t, {i, j}}); } } } vb s(n, true); while (!q.empty()) { int t = q.top().first; //cout << "at time " << -t << ": "; set<int> sh; while (!q.empty() && q.top().first == t) { int i = q.top().second.first, j = q.top().second.second; q.pop(); if (s[i]) sh.insert(i); if (s[j]) sh.insert(j); } if (sh.size() > 1) { while (!sh.empty()) { //cout << *sh.begin() << " "; s[*sh.begin()] = false; sh.erase(sh.begin()); } }// else cout << *sh.begin(); //cout << endl; } rep(i, n) { if (s[i]) cout << i+1 << " "; } cout << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vpl c(n); vpi d(n); rep(i,n) { char dir; cin >> c[i].first >> c[i].second >> dir; if (dir=='N') d[i] = {0, -1}; if (dir=='E') d[i] = {1, 0}; if (dir=='S') d[i] = {0, 1}; if (dir=='W') d[i] = {-1, 0}; } //cout << "done input" << endl; if (n==2) sub1(n, c, d); else sub5(n,c,d); return 0; }
#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...