Submission #1193912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193912		mmaiti	Naval battle (CEOI24_battle)	C++20	36 / 100	731 ms	44808 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);

  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;
    S[indMap[c]].push_back({x, y, i});
  }

  for (int i = 0; i < 4; i++) {
    map<int, map<int, Ship>> mp1, mp2;
    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[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[ix][key] = j;
    }
    // take care of the diagonals
    for (auto &k : mp1) {
      if (i <= 1) {
        for (auto j = k.second.begin(); j != k.second.end(); j++) {
          map<int, Ship>::iterator match;
          if (mp2[k.first].size() == 0)
            continue;
          if (i == 0)
            match = mp2[k.first].lower_bound(j->second.y);
          else
            match = mp2[k.first].lower_bound(j->second.x);
          if (match == mp2[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[k.first].erase(match);
        }
      } else {
        for (auto j = k.second.rbegin(); j != k.second.rend(); j++) {
          map<int, Ship>::iterator match;
          if (mp2[k.first].size() == 0)
            continue;
          if (i == 2)
            match = mp2[k.first].lower_bound(j->second.y);
          else
            match = mp2[k.first].lower_bound(j->second.x);
          if (match == mp2[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[k.first].erase(match);
        }
      }
    }
  }

  for (int i : {2, 3}) {
    map<int, map<int, Ship>> mp1, mp2;
    for (auto j : S[i]) {
      int ix = (i == 2 ? j.x : j.y);
      int rix = (i == 2 ? j.y : j.x);
      mp1[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);
      mp2[ix][rix] = j;
    }

    for (auto &k : mp1) {
      for (auto j = k.second.begin(); j != k.second.end(); j++) {
        map<int, Ship>::iterator match;
        if (i == 2)
          match = mp2[k.first].lower_bound(j->second.y);
        else
          match = mp2[k.first].lower_bound(j->second.x);
        if (match == mp2[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));
        mp2[k.first].erase(match);
      }
    }
  }

  vb active(N, true);
  ll tprev = -1;
  vll buffer;
  while (!pq.empty()) {
    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);
    }
    tprev = t;
  }
  for (auto j : buffer)
    active[j] = false;
  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: 30 / 30
• Subtask 7: 0 / 24