Submission #1196254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196254		mmaiti	Naval battle (CEOI24_battle)	C++20	100 / 100	349 ms	104200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>

#define MAXN 2000005
int n;
pii arr[MAXN];
char c[MAXN];
bool dead[MAXN];

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
               greater<tuple<int, int, int>>>
    pq;
struct dat {
  vector<int> idx;
  pii cmp1, cmp2;
  char ca, cb;

  int nx[MAXN];
  int pv[MAXN];
  int dot(pii p1, pii p2) {
    return p1.first * p2.first + p1.second * p2.second;
  }

  bool can(int i, int j) {
    return dot(arr[i], cmp1) == dot(arr[j], cmp1) && c[i] == ca && c[j] == cb;
  }

  int dist(int i, int j) {
    return abs(arr[i].first - arr[j].first) +
           abs(arr[i].second - arr[j].second);
  }

  void init() {
    memset(nx, -1, sizeof(nx));
    memset(pv, -1, sizeof(pv));
    if (idx.empty())
      return;
    sort(idx.begin(), idx.end(), [&](int &p1, int &p2) {
      pii a = arr[p1], b = arr[p2];
      if (dot(a, cmp1) == dot(b, cmp1))
        return dot(a, cmp2) < dot(b, cmp2);
      return dot(a, cmp1) < dot(b, cmp1);
    });
    for (int i = 0; i < (int)idx.size() - 1; i++) {
      nx[idx[i]] = idx[i + 1];
      pv[idx[i + 1]] = idx[i];

      if (can(idx[i], idx[i + 1])) {
        pq.push({dist(idx[i], idx[i + 1]), idx[i], idx[i + 1]});
      }
    }
  }

  void rem(int i) {
    int nn = nx[i], pp = pv[i];
    if (pp != -1)
      nx[pp] = nn;
    if (nn != -1)
      pv[nn] = pp;
    if (pp != -1 && nn != -1 && can(pp, nn))
      pq.push({dist(pp, nn), pp, nn});
  }
};

dat st[6];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i].first >> arr[i].second >> c[i];
  }

  // NW, NE, SE, SW, NS, EW
  st[0].cmp1 = {1, 1}, st[0].cmp2 = {1, 0}, st[0].ca = 'N', st[0].cb = 'W';
  st[1].cmp1 = {-1, 1}, st[1].cmp2 = {1, 0}, st[1].ca = 'E', st[1].cb = 'N';
  st[2].cmp1 = {1, 1}, st[2].cmp2 = {1, 0}, st[2].ca = 'E', st[2].cb = 'S';
  st[3].cmp1 = {-1, 1}, st[3].cmp2 = {1, 0}, st[3].ca = 'S', st[3].cb = 'W';
  st[4].cmp1 = {1, 0}, st[4].cmp2 = {0, 1}, st[4].ca = 'S', st[4].cb = 'N';
  st[5].cmp1 = {0, 1}, st[5].cmp2 = {1, 0}, st[5].ca = 'E', st[5].cb = 'W';
  /*st[0].cmp1 = {1, -1}, st[0].cmp2 = {1, 0}, st[0].ca = 'E', st[0].cb = 'N';*/
  /*st[1].cmp1 = {1, 1}, st[1].cmp2 = {1, 0}, st[1].ca = 'N', st[1].cb = 'W';*/
  /*st[2].cmp1 = {1, 1}, st[2].cmp2 = {1, 0}, st[2].ca = 'E', st[2].cb = 'S';*/
  /*st[3].cmp1 = {1, -1}, st[3].cmp2 = {1, 0}, st[3].ca = 'S', st[3].cb = 'W';*/
  /*st[4].cmp1 = {1, 0}, st[4].cmp2 = {0, 1}, st[4].ca = 'S', st[4].cb = 'N';*/
  /*st[5].cmp1 = {0, 1}, st[5].cmp2 = {1, 0}, st[5].ca = 'E', st[5].cb = 'W';*/

  map<char, vector<int>> M = {
      {'N', {0, 1, 4}}, {'E', {1, 2, 5}}, {'S', {2, 3, 4}}, {'W', {0, 3, 5}}};
  for (int i = 0; i < n; i++) {
    for (int j : M[c[i]]) {
      st[j].idx.push_back(i);
    }
  }
  for (int i = 0; i < 6; i++)
    st[i].init();

  while (!pq.empty()) {
    int w, a, b;
    tie(w, a, b) = pq.top();
    pq.pop();
    if (dead[a] || dead[b])
      continue;

    si tm = {a, b};
    while (!pq.empty() && get<0>(pq.top()) == w) {
      tie(w, a, b) = pq.top();
      pq.pop();
      if (!dead[a] && !dead[b]) {
        tm.insert(a);
        tm.insert(b);
      }
    }

    for (int i : tm) {
      dead[i] = true;
      for (auto it : M[c[i]])
        st[it].rem(i);
    }
  }
  for (int i = 0; i < n; i++)
    if (!dead[i])
      cout << i + 1 << "\n";
}

• 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