Submission #1068830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068830		huutuan	Naval battle (CEOI24_battle)	C++14	0 / 100	1048 ms	460292 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10, dx[]={0, 0, 1, -1}, dy[]={-1, 1, 0, 0};
const string dir="NSEW";
int n, x[N], y[N], d[N], t[N];
char c[N];

struct DS{
   int type;
   vector<int> v;
   vector<vector<int>> nxt, prv;
   void sort(){
      std::sort(v.begin(), v.end(), [&](int i, int j){ return tie(y[i], x[i])<tie(y[j], x[j]); });
   }
   void build(){
      prv=nxt=vector<vector<int>>(v.size(), vector<int>(4, -1));
      for (int i=1; i<(int)v.size(); ++i){
         prv[i]=prv[i-1];
         prv[i][d[v[i-1]]]=i-1;
      }
      for (int i=(int)v.size()-2; i>=0; --i){
         nxt[i]=nxt[i+1];
         nxt[i][d[v[i+1]]]=i+1;
      }
   }
   void solve(){
      if (type==1){
         for (int i=0; i<(int)v.size(); ++i){
            if (d[v[i]]==2 && nxt[i][3]!=-1){
               t[v[i]]=min(t[v[i]], (x[v[nxt[i][3]]]-x[v[i]])/2);
            }
            if (d[v[i]]==3 && prv[i][2]!=-1){
               t[v[i]]=min(t[v[i]], (x[v[i]]-x[v[prv[i][2]]])/2);
            }
         }
      }
      if (type==2){
         for (int i=0; i<(int)v.size(); ++i){
            if (d[v[i]]==1 && nxt[i][0]!=-1){
               t[v[i]]=min(t[v[i]], (y[v[nxt[i][0]]]-y[v[i]])/2);
            }
            if (d[v[i]]==0 && prv[i][1]!=-1){
               t[v[i]]=min(t[v[i]], (y[v[i]]-y[v[prv[i][1]]])/2);
            }
         }
      }
      if (type==3){
         for (int i=0; i<(int)v.size(); ++i){
            if (d[v[i]]==2 && nxt[i][0]!=-1){
               t[v[i]]=min(t[v[i]], y[v[nxt[i][0]]]-y[v[i]]);
            }
            if (d[v[i]]==0 && prv[i][2]!=-1){
               t[v[i]]=min(t[v[i]], y[v[i]]-y[v[prv[i][2]]]);
            }
            if (d[v[i]]==1 && nxt[i][3]!=-1){
               t[v[i]]=min(t[v[i]], y[v[nxt[i][3]]]-y[v[i]]);
            }
            if (d[v[i]]==3 && prv[i][1]!=-1){
               t[v[i]]=min(t[v[i]], y[v[i]]-y[v[prv[i][1]]]);
            }
         }
      }
      if (type==4){
         for (int i=0; i<(int)v.size(); ++i){
            if (d[v[i]]==3 && nxt[i][0]!=-1){
               t[v[i]]=min(t[v[i]], y[v[nxt[i][0]]]-y[v[i]]);
            }
            if (d[v[i]]==0 && prv[i][3]!=-1){
               t[v[i]]=min(t[v[i]], y[v[i]]-y[v[prv[i][3]]]);
            }
            if (d[v[i]]==1 && nxt[i][2]!=-1){
               t[v[i]]=min(t[v[i]], y[v[nxt[i][2]]]-y[v[i]]);
            }
            if (d[v[i]]==2 && prv[i][1]!=-1){
               t[v[i]]=min(t[v[i]], y[v[i]]-y[v[prv[i][1]]]);
            }
         }
      }
   }
};

map<int, DS> v1, v2, v3, v4;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i){
      cin >> x[i] >> y[i] >> c[i];
      t[i]=2e9;
      d[i]=dir.find(c[i]);
   }
   for (int i=1; i<=n; ++i){
      v1[y[i]].v.push_back(i);
      v2[x[i]].v.push_back(i);
      v3[x[i]-y[i]].v.push_back(i);
      v4[x[i]+y[i]].v.push_back(i);
   }
   for (auto &v:v1){
      v.second.sort(); v.second.build();
      v.second.type=1;
      v.second.solve();
   }
   for (auto &v:v2){
      v.second.sort(); v.second.build();
      v.second.type=2;
      v.second.solve();
   }
   for (auto &v:v3){
      v.second.sort(); v.second.build();
      v.second.type=3;
      v.second.solve();
   }
   for (auto &v:v4){
      v.second.sort(); v.second.build();
      v.second.type=4;
      v.second.solve();
   }
   map<pair<int, int>, int> mp;
   for (int i=1; i<=n; ++i) if (t[i]!=2e9){
      ++mp[{x[i]+dx[i]*t[i], y[i]+dy[i]*t[i]}];
   }
   for (int i=1; i<=n; ++i) if (t[i]==2e9 || mp[{x[i]+dx[i]*t[i], y[i]+dy[i]*t[i]}]>=2) cout << i << '\n';
   return 0;
}

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