Submission #1137574

#TimeUsernameProblemLanguageResultExecution timeMemory
1137574KaleemRazaSyedNaval battle (CEOI24_battle)C++20
46 / 100
765 ms106284 KiB
#include<bits/stdc++.h> using namespace std; const int inf = 2e9; pair<int,int> V(char c) { if(c == 'S') return {0, 1}; if(c == 'N') return {0, -1}; if(c == 'E') return {1, 0}; return {-1, 0}; } int D(int x1, int y1, char d1, int x2, int y2, char d2) { if(x1 == x2 && y1 == y2) return 0; if(d1 == d2) return inf; if(x1 < x2 && (V(d1).first == -1 || V(d2).first == 1 || (V(d1).first == 0 && V(d2).first == 0))) return inf; if(x1 > x2 && (V(d1).first == 1 || V(d2).first == -1 || (V(d1).first == 0 && V(d2).first == 0))) return inf; if(y1 < y2 && (V(d1).second == -1 || V(d2).second == 1 || (V(d1).second == 0 && V(d2).second == 0))) return inf; if(y1 > y2 && (V(d1).second == 1 || V(d2).second == -1 || (V(d1).second == 0 && V(d2).second == 0))) return inf; if(x1 == x2 && (V(d1).first != V(d2).first)) return inf; if(y1 == y2 && (V(d1).second != V(d2).second)) return inf; int tx = -1, ty = -1; if(x1 != x2) { int d = abs(V(d1).first) + abs(V(d2).first); tx = abs(x1 - x2) / d; } if(y1 != y2) { int d = abs(V(d1).second) + abs(V(d2).second); ty = abs(y1 - y2) / d; } if(tx == -1 || ty == -1 || tx == ty) return max(tx, ty); return inf; } void solve(int n) { vector<vector<int> > vec; int x[n], y[n]; char d[n]; int t[n] = {}; fill(t, t + n, inf); for(int i = 0; i < n; i ++) cin >> x[i] >> y[i] >> d[i]; for(int i = 0; i < n; i ++) for(int j = i + 1; j < n; j ++) { int X = D(x[i], y[i], d[i], x[j], y[j], d[j]); if(X != inf) vec.push_back({X, i, j}); } sort(vec.begin(), vec.end()); for(auto v : vec) { int d = v[0], i = v[1], j = v[2]; if(t[i] == inf && t[j] == inf) t[i] = t[j] = d; else if(t[i] == inf && t[j] == d) t[i] = d; else if(t[j] == inf && t[i] == d) t[j] = d; } for(int i = 0; i < n; i ++) if(t[i] == inf) cout << i + 1 << '\n'; } int main() { int n; cin >> n; if(n <= 5000) { solve(n); return 0; } vector<vector<int> > vec, st; char c[n]; bool dead[n] = {}; for(int i = 0; i < n; i ++) { int x, y; cin >> x >> y >> c[i]; vec.push_back({x, -y, i}); } sort(vec.begin(), vec.end()); for(int i = 1; i < n; i ++) if(vec[i - 1][0] == vec[i][0] && vec[i - 1][1] == vec[i][1]) dead[vec[i - 1][2]] = dead[vec[i][2]] = true; for(int i = 0; i < n; i ++) if(!dead[vec[i][2]]) st.push_back(vec[i]); set<vector<int> > S; int add = 0; for(int i = 0; i < st.size(); i ++) { if(i > 0) add -= st[i][0] - st[i - 1][0]; else add -= st[i][0]; if(c[st[i][2]] == 'E') S.insert({-st[i][1] - add, -st[i][0], st[i][2]}); else { auto it = S.lower_bound({-st[i][1] - add, -inf, -inf}); if(it == S.end() || it->at(0) != -st[i][1] - add) continue; dead[it->at(2)] = dead[st[i][2]] = true; S.erase(it); } } for(int i = 0; i < n; i ++) if(!dead[i]) cout << i << '\n'; 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...