Submission #1196104

#TimeUsernameProblemLanguageResultExecution timeMemory
1196104NeltNaval battle (CEOI24_battle)C++20
37 / 100
3103 ms1114112 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; struct pair_hash { std::size_t operator()(const std::pair<int, int>& p) const { return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1); } }; void solve() { int n; cin >> n; int x[n], y[n], dir[n]; unordered_set<pair<int, int>, pair_hash> cord[4]; map<pair<int, int>, int> ind; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; char c; cin >> c; ind[make_pair(x[i], y[i])] = i + 1; if (c == 'N') dir[i] = 0; else if (c == 'S') dir[i] = 1; else if (c == 'W') dir[i] = 2; else if (c == 'E') dir[i] = 3; cord[dir[i]].insert(make_pair(x[i], y[i])); } vector<array<int, 3>> event; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (dir[i] >= dir[j]) continue; // if (dir[i] == 0 and dir[j] == 1 and x[i] == x[j] and y[i] > y[j]) event.push_back({abs(y[i] - y[j]) / 2, x[i], (y[i] + y[j]) / 2}); // if (dir[i] == 2 and dir[j] == 3 and y[i] == y[j] and x[i] > x[j]) event.push_back({abs(x[i] - x[j]) / 2, (x[i] + x[j]) / 2, y[i]}); // if (dir[i] == 0 and dir[j] == 2 and x[i] + y[i] == x[j] + y[j]) event.push_back({abs(x[j] - x[i]), x[i], y[j]}); // if (dir[i] == 1 and dir[j] == 3 and x[i] + y[i] == x[j] + y[j]) // event.push_back({abs(x[i] - x[j]), x[i], y[j]}); // if (dir[i] == 0 and dir[j] == 3 and x[i] - y[i] == x[j] - y[j]) // event.push_back({abs(x[i] - x[j]), x[i], y[j]}); // if (dir[i] == 1 and dir[j] == 2 and x[i] - y[i] == x[j] - y[j]) // event.push_back({abs(x[j] - x[i]), x[i], y[j]}); } sort(event.begin(), event.end()); int c0, c1, c2, c3; for (auto [tim, x, y] : event) { c0 = cord[0].count(make_pair(x, y + tim)); c1 = cord[1].count(make_pair(x, y - tim)); c2 = cord[2].count(make_pair(x + tim, y)); c3 = cord[3].count(make_pair(x - tim, y)); if (c0 + c1 + c2 + c3 <= 1) continue; if (c0) cord[0].erase(make_pair(x, y + tim)); if (c1) cord[1].erase(make_pair(x, y - tim)); if (c2) cord[2].erase(make_pair(x + tim, y)); if (c3) cord[3].erase(make_pair(x - tim, y)); } for (auto i : cord) for (auto j : i) cout << ind[j] << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\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...