Submission #1192938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192938		mmaiti	Naval battle (CEOI24_battle)	C++20	6 / 100	3032 ms	793084 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;

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

  if ((x2 - x1) % (mult1 - mult2) == 0)
    return (x2 - x1) / (mult1 - mult2);
  return 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;
  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]);
      ll t1 = solveEq(x1, dirs[dir1].first, x2, dirs[dir2].first);
      ll t2 = solveEq(y1, dirs[dir1].second, y2, dirs[dir2].second);
      if (t1 == t2 && t1 != INF && t1 >= 0) {
        pq.push(make_tuple(t1, 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 (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: 0 / 30
• Subtask 7: 0 / 24