제출 #1193942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193942		mmaiti	Naval battle (CEOI24_battle)	C++20	6 / 100	3098 ms	107784 KiB

Main

#include <bits/stdc++.h>
#include <queue>
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>>

void printTuple(tuple<ll, ll, char> &t) {
  cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
}

struct Ship {
  int x, y, ix;
};
void solve() {
  // need 3 different ways of sorting
  // 0. along x + y
  // 1. along x - y
  // 2. along the direction of travel (y for N/S, x for E/W)
  ll N;
  cin >> N;
  vector<vector<Ship>> S(4);
  vector<pii> shipCoord(N);
  vector<char> shipDir(N);

  map<char, int> indMap;
  indMap['N'] = 0;
  indMap['W'] = 1;
  indMap['S'] = 2;
  indMap['E'] = 3;

  priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>,
                 greater<tuple<ll, ll, ll>>>
      pq;
  int x, y;
  char c;
  for (int i = 0; i < N; i++) {
    cin >> x >> y >> c;
    shipCoord[i] = {x, y};
    shipDir[i] = c;
    S[indMap[c]].push_back({x, y, i});
  }

  vb active(N, true);
  vector<map<int, map<int, Ship>>> mp1(4), mp2(4), mp3(4), mp4(4);
  for (int i = 0; i < 4; i++) {
    for (auto j : S[i]) {
      int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
      int key = (i % 2 == 0) ? j.y : j.x;
      mp1[i][ix][key] = j;
    }
    for (auto j : S[(i + 1) % 4]) {
      int ix = j.x + (i % 2 == 0 ? 1 : -1) * j.y;
      int key = (i % 2 == 0) ? j.y : j.x;
      mp2[i][ix][key] = j;
    }
  }
  for (int i : {2, 3}) {
    for (auto j : S[i]) {
      int ix = (i == 2 ? j.x : j.y);
      int rix = (i == 2 ? j.y : j.x);
      mp3[i][ix][rix] = j;
    }
    for (auto j : S[(i + 2) % 4]) {
      int ix = (i == 2 ? j.x : j.y);
      int rix = (i == 2 ? j.y : j.x);
      mp4[i][ix][rix] = j;
    }
  }

  bool cont = true;
  while (cont) {
    cont = false;
    // actual logic is here
    for (int i = 0; i < 4; i++) {
      // take care of the diagonals
      for (auto &k : mp1[i]) {
        if (i <= 1) {
          while (k.second.size() > 0 && !active[k.second.begin()->second.ix])
            k.second.erase(k.second.begin());
          if (k.second.empty())
            continue;
          auto j = k.second.begin();

          map<int, Ship>::iterator match;
          if (mp2[i][k.first].size() == 0)
            continue;
          if (i == 0)
            match = mp2[i][k.first].lower_bound(j->second.y);
          else
            match = mp2[i][k.first].lower_bound(j->second.x);
          if (match == mp2[i][k.first].begin())
            continue;
          --match;
          int xdiff = abs(j->second.x - match->second.x);
          pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
          mp2[i][k.first].erase(match);
        } else {
          while (k.second.size() > 0 && !active[k.second.rbegin()->second.ix])
            k.second.erase(--k.second.end());
          if (k.second.empty())
            continue;
          auto j = k.second.rbegin();
          map<int, Ship>::iterator match;
          if (mp2[i][k.first].size() == 0)
            continue;
          if (i == 2)
            match = mp2[i][k.first].lower_bound(j->second.y);
          else
            match = mp2[i][k.first].lower_bound(j->second.x);
          if (match == mp2[i][k.first].end())
            continue;
          int xdiff = abs(j->second.x - match->second.x);
          pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
          mp2[i][k.first].erase(match);
        }
      }
    }

    for (int i : {2, 3}) {
      for (auto &k : mp3[i]) {
        while (k.second.size() > 0 && !active[k.second.rbegin()->second.ix])
          k.second.erase(--k.second.end());
        if (k.second.empty())
          continue;
        auto j = k.second.rbegin();
        map<int, Ship>::iterator match;
        if (i == 2) {
          match = mp4[i][k.first].lower_bound(j->second.y);
        } else {
          match = mp4[i][k.first].lower_bound(j->second.x);
        }
        if (match == mp4[i][k.first].end())
          continue;
        int diff = (i == 2) ? abs(j->second.y - match->second.y) / 2
                            : abs(j->second.x - match->second.x) / 2;

        pq.push(make_tuple(diff, j->second.ix, match->second.ix));
        mp4[i][k.first].erase(match);
      }
    }

    ll tprev = -1;
    vll buffer;
    vll repush;
    while (!pq.empty()) {
      cont = true;
      auto [t, x, y] = pq.top();
      if (t > tprev) {
        for (auto j : buffer)
          active[j] = false;
        buffer.clear();
      }
      pq.pop();
      if (active[x] && active[y]) {
        buffer.push_back(x);
        buffer.push_back(y);
      } else {
        repush.push_back(x);
        repush.push_back(y);
      }
      tprev = t;
    }
    for (auto j : buffer)
      active[j] = false;
    for (int i : repush) {
      if (active[i]) {
        int curDir = indMap[shipDir[i]];
        Ship j = {shipCoord[i].first, shipCoord[i].second, curDir};
        int ni = (curDir + 4 - 1) % 4;
        int n2i = (curDir - 2 + 4) % 4;
        int ix = j.x + (ni % 2 == 0 ? 1 : -1) * j.y;
        int key = (ni % 2 == 0) ? j.y : j.x;
        mp2[ni][ix][key] = j;

        if (curDir == 0 || curDir == 1) {
          int ix = (n2i == 2 ? j.x : j.y);
          int rix = (n2i == 2 ? j.y : j.x);
          mp4[n2i][ix][rix] = j;
        }
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (active[i])
      cout << i + 1 << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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