제출 #1290043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290043		loom	Naval battle (CEOI24_battle)	C++20	100 / 100	1008 ms	101908 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)5e18
#define nl '\n'

void solve(){
   int n;
   cin>>n;

   map<int, set<array<int,3>>> mp[6];
   vector<tuple<int,int,char>> v(n);

   for(int i = 0; i < n; i++){
      auto &[x, y, d] = v[i];
      cin>>x>>y>>d;
      swap(x, y);

      if(d == 'E'){
         mp[0][x-y].insert({x, 0, i});
         mp[1][x+y].insert({x, 1, i});
         mp[2][x].insert({y/2, 0, i});
      }
      if(d == 'N'){
         mp[0][x-y].insert({x, 1, i});
         mp[3][y].insert({x/2, 1, i});
         mp[4][x+y].insert({x, 1, i});
      }
      if(d == 'S'){
         mp[1][x+y].insert({x, 0, i});
         mp[3][y].insert({x/2, 0, i});
         mp[5][x-y].insert({x, 0, i});
      }
      if(d == 'W'){
         mp[2][x].insert({y/2, 1, i});
         mp[4][x+y].insert({x, 0, i});
         mp[5][x-y].insert({x, 1, i});
      }
   }

   priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;

   for(int w = 0; w < 6; w++){
      for(auto &[x, st] : mp[w]){
         auto pit = st.begin(), it = st.begin();

         while(++it != st.end()){
            auto [p1, d1, i1] = *pit;
            auto [p2, d2, i2] = *it;

            if(!d1 and d2) pq.push({p2 - p1, i1, i2});
            pit++;
         }
      }
   }

   auto del = [&](int m, int w, int p, int d, int i){
      auto &st = mp[m][w];
      auto it = st.find({p, d, i});
      
      it = st.erase(it);
      if(it == st.begin() or it == st.end()) return;
      auto pit = prev(it);

      auto [p1, d1, i1] = *pit;
      auto [p2, d2, i2] = *it;

      if(!d1 and d2) pq.push({p2 - p1, i1, i2});
   };

   auto rem = [&](int i){
      auto [x, y, d] = v[i];

      if(d == 'E'){
         del(0, x-y, x, 0, i);
         del(1, x+y, x, 1, i);
         del(2, x, y/2, 0, i);
      }
      if(d == 'N'){
         del(0, x-y, x, 1, i);
         del(3, y, x/2, 1, i);
         del(4, x+y, x, 1, i);
      }
      if(d == 'S'){
         del(1, x+y, x, 0, i);
         del(3, y, x/2, 0, i);
         del(5, x-y, x, 0, i);
      }
      if(d == 'W'){
         del(2, x, y/2, 1, i);
         del(4, x+y, x, 0, i);
         del(5, x-y, x, 1, i);
      }
   };

   vector<int> dt(n);

   while(!pq.empty()){
      auto [t, i1, i2] = pq.top();
      pq.pop();

      if((dt[i1] or dt[i2]) and dt[i1] != t and dt[i2] != t) continue;

      if(!dt[i1]) rem(i1);
      if(!dt[i2]) rem(i2);
      dt[i1] = dt[i2] = t;
   }

   for(int i = 0; i < n; i++) if(!dt[i]) cout<<i+1<<nl;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 24 / 24