Submission #1254165

#TimeUsernameProblemLanguageResultExecution timeMemory
1254165glupanNaval battle (CEOI24_battle)C++20
46 / 100
439 ms229212 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MOD = 1e9 + 7; const int INF = 1e9; const int MAX_N = 1e5 + 5; void solve() { int n; cin >> n; int x[n],y[n]; char d[n]; for(int i=0; i<n; i++) { cin >> x[i] >> y[i] >> d[i]; } if(n <= 5000) { vector<vector<ll>> sudar(n+1, vector<ll>(n+1, 1e18)); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(d[i] == d[j]) { continue; } if(d[i] == 'S') { if(d[j] == 'N') { if(x[i] == x[j] and y[i] < y[j]) { sudar[i][j] = (y[j]-y[i]) / 2; } } else if(d[j] == 'E') { if(x[i] + y[i] == x[j] + y[j] and y[i] < y[j]) { sudar[i][j] = y[j] - y[i]; } } else if(d[j] == 'W') { if(x[i] - y[i] == x[j] - y[j] and y[i] < y[j]) { sudar[i][j] = y[j] - y[i]; } } } else if(d[i] == 'N') { if(d[j] == 'E') { if(x[i] - y[i] == x[j] - y[j] and y[i] > y[j]) { sudar[i][j] = y[i] - y[j]; } } else if(d[j] == 'W') { if(x[i] + y[i] == x[j] + y[j] and y[i] > y[j]) { sudar[i][j] = y[i] - y[j]; } } } else if(d[i] == 'E') { if(d[j] == 'W') { if(y[i] == y[j] and x[i] < x[j]) { sudar[i][j] = (x[j]-x[i]) / 2; } } } } } vector<pair<ll,pair<int,int>>>v; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(sudar[i][j] != 1e18) { v.push_back({sudar[i][j], {i,j}}); } } } sort(v.begin(), v.end()); vector<int>blown(n+1,0); for(auto x : v) { //cout << x.first << " " << x.second.first << " " << x.second.second << endl; if(blown[x.second.first] > 0 and blown[x.second.first] != x.first or blown[x.second.second] > 0 and blown[x.second.second] != x.first) continue; blown[x.second.first] = x.first; blown[x.second.second] = x.first; } for(int i=0; i<n; i++) { if(!blown[i]) cout << i+1 << endl; } } else { map<ll,int> m; for(int i=0; i<n; i++) { if(d[i] == 'S') { if(!m[x[i]+y[i]]) m[x[i]+y[i]] = i+1; } } vector<pair<pair<int, char>,pair<int,int>>>v[n+1]; for(int i=0; i<n; i++) { if(m[x[i]+y[i]]) { v[m[x[i]+y[i]]].push_back({{i, d[i]}, {x[i],y[i]}}); } } vector<int>blown(n+1,0); for(int i=1; i<=n; i++) { if(v[i].size()) { sort(v[i].begin(), v[i].end()); queue<int> east, south; for(int j=0; j<v[i].size(); j++) { if(v[i][j].first.second == 'S') south.push(v[i][j].first.first); else east.push(v[i][j].first.first); } while(!east.empty() and !south.empty()) { int E = east.front(), S = south.front(); blown[E] = 1; blown[S] = 1; east.pop(); south.pop(); } } } for(int i=0; i<n; i++) { if(!blown[i]) cout << i+1 << endl; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int tc=1; while(tc--) solve(); }
#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...