Submission #1134349

#TimeUsernameProblemLanguageResultExecution timeMemory
1134349ReLiceNaval battle (CEOI24_battle)C++20
20 / 100
43 ms12216 KiB
#include <bits/stdc++.h> #define ll long long #define ld double #define pb push_back #define pf push_front #define ins insert #define fr first #define sc second #define endl "\n" #define ar array #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);} void solve() { ll i, j; ll n; cin>>n; ll x[n + 1], y[n + 1]; ll d[n + 1]; vector<ll> vv; vector<ar<ll, 3>> ans; bool ff = 1; for(i=1;i<=n;i++){ char ch; cin>>x[i]>>y[i]>>ch; if(ch == 'N') d[i] = 0; if(ch == 'S') d[i] = 1; if(ch == 'W') d[i] = 2; if(ch == 'E') d[i] = 3; if(ch == 'N') ff = 0; if(ch == 'W') ff = 0; vv.pb(x[i] + y[i]); } if(ff){ sort(all(vv)); vv.erase(unique(all(vv)), vv.end()); map<ll,ll> pos; for(i=0;i<vv.size();i++){ pos[vv[i]] = i; } vector<vector<pair<ll,ll>>> v(vv.size()), h(vv.size()); for(i=1;i<=n;i++){ if(d[i] == 1) v[pos[x[i] + y[i]]].pb({x[i], i}); else h[pos[x[i] + y[i]]].pb({x[i], i}); } for(i=0;i<vv.size();i++) sort(all(vv)); for(i=0;i<vv.size();i++){ ll a = 0, b = 0; while(a < v[i].size()){ while(b < h[i].size() && v[i][a].fr >= h[i][b].fr) b++; if(b == h[i].size()) break; ans.pb({h[i][b].fr - v[i][a].fr, v[i][a].sc, h[i][b].sc}); a++; } } } else{ for(i=1;i<=n;i++){ for(j=i + 1;j<=n;j++){ if(d[i] == d[j]) continue; if(d[i] > d[j]) swap(i, j); if(d[i] == 0 && d[j] == 1 && x[i] == x[j] && y[j] < y[i]){ ans.pb({(y[i] - y[j]) / 2, i, j}); } if(d[i] == 2 && d[j] == 3 && y[i] == y[j] && x[i] > x[j]){ ans.pb({(x[i] - x[j]) / 2, i, j}); } if(d[i] <= 1 && d[j] >= 2){ bool f = 0; if(d[i] == 0 && d[j] == 2 && x[j] - x[i] == y[i] - y[j] && x[j] > x[i]) f = 1; if(d[i] == 0 && d[j] == 3 && x[i] - x[j] == y[i] - y[j] && x[i] > x[j]) f = 1; if(d[i] == 1 && d[j] == 2 && x[j] - x[i] == y[j] - y[i] && x[j] > x[i]) f = 1; if(d[i] == 1 && d[j] == 3 && x[i] - x[j] == y[j] - y[i] && x[i] > x[j]) f = 1; if(f){ ans.pb({abs(x[i] - x[j]), i, j}); } } if(i > j) swap(i, j); } } } vector<bool> f(n + 1, true); sort(rall(ans)); while(ans.size()){ vector<ll> vv; ll x = ans.back()[0]; while(ans.size() && ans.back()[0] == x){ i = ans.back()[1], j = ans.back()[2]; ans.pop_back(); if(f[i] && f[j]){ vv.pb(i); vv.pb(j); } } for(auto i : vv){ f[i] = 0; } } for(i=1;i<=n;i++) { if(f[i]) cout<<i<<endl; } } signed main(){ start(); ll t = 1; //cin>>t; while(t--) 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...