제출 #1074036

#제출 시각아이디문제언어결과실행 시간메모리
1074036GrindMachineNaval battle (CEOI24_battle)C++17
30 / 100
3032 ms103120 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define conts continue #define sz(a) (int)a.size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &x, T y){ x = min(x,y); } template<typename T> void amax(T &x, T y){ x = max(x,y); } template<typename A,typename B> string to_string(pair<A,B> p); string to_string(const string &s){ return "'"+s+"'"; } string to_string(const char* s){ return to_string((string)s); } string to_string(bool b){ return b?"true":"false"; } template<typename A> string to_string(A v){ string res = "{"; trav(x,v){ res += to_string(x)+","; } if(res.back() == ',') res.pop_back(); res += "}"; return res; } template<typename A,typename B> string to_string(pair<A,B> p){ return "("+to_string(p.ff)+","+to_string(p.ss)+")"; } #define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = 1e9 + 5; const ll inf2 = (ll)1e18 + 5; void solve(int test_case){ int n; cin >> n; vector<array<int,3>> a(n+5); rep1(i,n){ int r,c; cin >> r >> c; char ch; cin >> ch; swap(r,c); int d = -1; if(ch == 'E') d = 0; if(ch == 'W') d = 1; if(ch == 'S') d = 2; if(ch == 'N') d = 3; a[i] = {r,c,d}; } auto f = [&](int i, int j){ if(a[i][2] > a[j][2]) swap(i,j); auto [ri,ci,di] = a[i]; auto [rj,cj,dj] = a[j]; if(di == dj) return 2*inf1; int t = 2*inf1; if((di^1) == dj){ if(di == 0){ if(ri == rj and ci <= cj){ t = (cj-ci)/2; } } else{ if(ci == cj and ri <= rj){ t = (rj-ri)/2; } } } else{ assert(di == 0 or di == 1); if(di == 0){ if(ci <= cj){ if(dj == 2){ if(ri-rj == cj-ci){ t = abs(ri-rj); } } else{ if(rj-ri == cj-ci){ t = abs(ri-rj); } } } } else{ if(ci >= cj){ if(dj == 2){ if(ri-rj == ci-cj){ t = abs(ri-rj); } } else{ if(rj-ri == ci-cj){ t = abs(ri-rj); } } } } } return t; }; map<int,set<pii>> mp[4][2]; vector<vector<int>> dt = { {0,1}, {2,3}, {0,2}, {1,3} }; rep1(i,n){ auto [r,c,d] = a[i]; array<int,4> keys = {r,c,r+c,r-c}; rep(j,4){ int id = find(all(dt[j]),d)-dt[j].begin(); if(id <= 1){ int val = c; if(j&1) val = r; mp[j][id][keys[j]].insert({val,i}); } } } priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq; auto nxt_collision = [&](int i, int j) -> array<int,3>{ auto [r,c,d] = a[i]; int id = find(all(dt[j]),d)-dt[j].begin(); if(id >= 2) return {-1,-1,-1}; int val = c; if(j&1) val = r; array<int,4> keys = {r,c,r+c,r-c}; auto &st = mp[j][id^1][keys[j]]; auto it = st.upper_bound({val,-1}); int k = -1; if(id == 0){ if(it != st.end()){ k = it->ss; } } else{ if(it != st.begin()){ it--; k = it->ss; } } if(k != -1){ int t = f(i,k); pq.push({t,i,k}); return {t,i,k}; } return {-1,-1,-1}; }; rep1(i,n){ rep(j,4){ nxt_collision(i,j); } } vector<bool> rem(n+5); while(!pq.empty()){ int mnt = 2*inf1+1; vector<int> del; while(!pq.empty()){ auto [t,i,j] = pq.top(); if(t > mnt) break; if(t == 2*inf1) break; pq.pop(); if(rem[i] or rem[j]){ rep(x,4){ if(!rem[i]){ nxt_collision(i,x); } if(!rem[j]){ nxt_collision(j,x); } } conts; } mnt = t; del.pb(i), del.pb(j); } trav(i,del){ if(rem[i]) conts; rem[i] = 1; auto [r,c,d] = a[i]; array<int,4> keys = {r,c,r+c,r-c}; rep(j,4){ int id = find(all(dt[j]),d)-dt[j].begin(); if(id <= 1){ int val = c; if(j&1) val = r; mp[j][id][keys[j]].erase({val,i}); } } } } vector<int> ans; rep1(i,n){ if(!rem[i]){ ans.pb(i); } } trav(x,ans) cout << x << endl; // while(true){ // mnt = inf1; // del.clear(); // for(auto &[val,st] : mpr){ // ll prev_occ[4]; // memset(prev_occ,-1,sizeof prev_occ); // for(auto [v1,i] : st){ // rep(d,4){ // int j = prev_occ[d]; // if(j != -1){ // upd(i,j); // } // } // prev_occ[a[i][2]] = i; // } // } // for(auto &[val,st] : mpc){ // ll prev_occ[4]; // memset(prev_occ,-1,sizeof prev_occ); // for(auto [v1,i] : st){ // rep(d,4){ // int j = prev_occ[d]; // if(j != -1){ // upd(i,j); // } // } // prev_occ[a[i][2]] = i; // } // } // for(auto &[val,st] : mpsum){ // ll prev_occ[4]; // memset(prev_occ,-1,sizeof prev_occ); // for(auto [v1,i] : st){ // rep(d,4){ // int j = prev_occ[d]; // if(j != -1){ // upd(i,j); // } // } // prev_occ[a[i][2]] = i; // } // } // for(auto &[val,st] : mpdiff){ // ll prev_occ[4]; // memset(prev_occ,-1,sizeof prev_occ); // for(auto [v1,i] : st){ // rep(d,4){ // int j = prev_occ[d]; // if(j != -1){ // upd(i,j); // } // } // prev_occ[a[i][2]] = i; // } // } // if(mnt == inf1) break; // trav(i,del){ // rem[i] = 1; // auto [r,c,d] = a[i]; // mpr[r].erase({c,i}); // mpc[c].erase({r,i}); // mpsum[r+c].erase({c,i}); // mpdiff[r-c].erase({c,i}); // } // } // vector<int> ans; // rep1(i,n){ // if(!rem[i]){ // ans.pb(i); // } // } // trav(x,ans) cout << x << endl; } int main(){ fastio; int t = 1; // cin >> t; rep1(i,t){ solve(i); } 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...