제출 #1192963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192963		mmaiti	Naval battle (CEOI24_battle)	C++20	46 / 100	3120 ms	793236 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>>

const ll INF = 1e17;

pll solveEq(ll x1, ll mult1, ll x2, ll mult2) {
  if (mult1 == mult2) {
    return (x1 == x2) ? make_pair(0LL, INF) : make_pair(-INF, -INF);
  }
  // now mult1 != mult2

  if ((x2 - x1) % (mult1 - mult2) == 0) {
    ll ans = (x2 - x1) / (mult1 - mult2);
    return {ans, ans};
  }
  return {-INF, -INF};
}

void printTuple(tuple<ll, ll, char> &t) {
  cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
}
void solve() {
  ll N;
  cin >> N;
  vector<tuple<ll, ll, char>> S(N);
  map<char, pll> dirs;
  dirs['N'] = {0, -1};
  dirs['S'] = {0, 1};
  dirs['E'] = {1, 0};
  dirs['W'] = {-1, 0};
  for (int i = 0; i < N; i++) {
    cin >> get<0>(S[i]) >> get<1>(S[i]) >> get<2>(S[i]);
  }
  priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>,
                 greater<tuple<ll, ll, ll>>>
      pq;

  auto inR = [&](ll t) { return (t >= 0) && t < INF; };
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
      ll x1 = get<0>(S[i]), x2 = get<0>(S[j]);
      ll y1 = get<1>(S[i]), y2 = get<1>(S[j]);
      char dir1 = get<2>(S[i]), dir2 = get<2>(S[j]);
      auto t1 = solveEq(x1, dirs[dir1].first, x2, dirs[dir2].first);
      auto t2 = solveEq(y1, dirs[dir1].second, y2, dirs[dir2].second);
      auto inter =
          make_pair(max(t1.first, t2.first), min(t1.second, t2.second));
      if (inter.second >= 0 && inter.second >= inter.first)
        pq.push({inter.second, i, j});
    }
  }
  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 (x == 2 || y == 2)*/
    /*  cout << t << " " << x << " " << y << " " << active[x] << " " <<
     * active[y]*/
    /*       << endl;*/
    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: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24