Submission #1196184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196184		mmaiti	Naval battle (CEOI24_battle)	C++20	6 / 100	443 ms	108496 KiB

Main

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

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<int> 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] = indMap[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;
    }
  }

  auto pushMp4 = [&](int i, map<int, map<int, Ship>>::iterator &k) {
    if (k->second.empty()) {
      k++;
      return;
    }
    auto j = k->second.rbegin();
    map<int, Ship>::iterator match;
    if (mp4[i][k->first].size() == 0) {
      k++;
      return;
    }
    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()) {
      k++;
      return;
    }
    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);
    k++;
  };

  auto pushMp2 = [&](int i, map<int, map<int, Ship>>::iterator &k) {
    if (k->second.empty()) {
      k++;
      return;
    }
    if (i <= 1) {
      auto j = k->second.begin();
      map<int, Ship>::iterator match;
      if (mp2[i][k->first].size() == 0) {
        k++;
        return;
      }
      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()) {
        k++;
        return;
      }
      --match;
      int xdiff = abs(j->second.x - match->second.x);
      pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
    } else {
      auto j = k->second.rbegin();
      map<int, Ship>::iterator match;
      if (mp2[i][k->first].size() == 0) {
        k++;
        return;
      }
      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()) {
        k++;
        return;
      }
      int xdiff = abs(j->second.x - match->second.x);
      pq.push(make_tuple(xdiff, j->second.ix, match->second.ix));
    }
    k++;
  };
  // setup priority queue first
  for (int i = 0; i < 4; i++) {
    // take care of the diagonals
    for (auto k = mp1[i].begin(); k != mp1[i].end();) {
      pushMp2(i, k);
    }
  }

  for (int i : {2, 3}) {
    for (auto k = mp3[i].begin(); k != mp3[i].end();) {
      pushMp4(i, k);
    }
  }

  auto remDir1 = [&](int dir, int ix, vector<map<int, map<int, Ship>>> &mp) {
    if (dir % 2 == 0) {
      int val = shipCoord[ix].first + shipCoord[ix].second;
      int key = shipCoord[ix].second;
      mp[dir][val].erase(key);
    } else {
      int val = shipCoord[ix].first - shipCoord[ix].second;
      int key = shipCoord[ix].first;
      mp[dir][val].erase(key);
    }
  };

  auto remove = [&](int ix) {
    int curDir = shipDir[ix];
    // remove from mp1, mp2
    remDir1(curDir, ix, mp1);
    remDir1((curDir - 1 + 4) % 4, ix, mp2);

    // remove from mp3, mp4
    if (curDir == 2 || curDir == 3) {
      // removing from mp3
      if (curDir == 2) {
        mp3[curDir][shipCoord[ix].first].erase(shipCoord[ix].second);
      } else {
        mp3[curDir][shipCoord[ix].second].erase(shipCoord[ix].first);
      }
    } else {
      // removing from mp4
      if (curDir == 0) {
        mp4[curDir][shipCoord[ix].first].erase(shipCoord[ix].second);
      } else {
        mp4[curDir][shipCoord[ix].second].erase(shipCoord[ix].first);
      }
    }
  };
  ll tprev = -1;
  vector<pll> buffer;

  auto clearBuffer = [&]() {
    for (auto pr : buffer) {
      // remove x and y from the maps
      // each needs to be removed from mp1, mp2, and either mp3 or mp4
      if (active[pr.first])
        remove(pr.first);
      if (active[pr.second])
        remove(pr.second);
      active[pr.first] = false;
      active[pr.second] = false;
      // ships were on the same diagonal
      if ((shipDir[pr.second] - shipDir[pr.first] + 4) % 4 == 1) {
        // check if the diagonal was x + pr.second or x - pr.second
        if (shipDir[pr.first] % 2 == 0) {
          auto it = mp1[shipDir[pr.first]].find(shipCoord[pr.first].first +
                                                shipCoord[pr.first].second);
          pushMp2(shipDir[pr.first], it);
        } else {
          auto it = mp1[shipDir[pr.first]].find(shipCoord[pr.first].first -
                                                shipCoord[pr.first].second);
          pushMp2(shipDir[pr.first], it);
        }
      } else {
        // check if it was horizontal or vertical
        if (shipDir[pr.first] == 2) {
          auto it = mp3[shipDir[pr.first]].find(shipCoord[pr.first].first);
          pushMp4(shipDir[pr.first], it);
        } else {
          auto it = mp3[shipDir[pr.first]].find(shipCoord[pr.first].second);
          pushMp4(shipDir[pr.first], it);
        }
      }
    }
  };
  while (!pq.empty()) {
    auto [t, x, y] = pq.top();
    if (t > tprev) {
      clearBuffer();
      buffer.clear();
    } else {
      pq.pop();
      if (active[x] && active[y]) {
        buffer.push_back({x, y});
      }
    }
    tprev = t;
  }
  clearBuffer();
  buffer.clear();
  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