108432024-04-16 14:44:46Leventusz09Particlescpp17Wrong answer 0/100108ms8888 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Particle {
  int type; // 0: x-részecske, 1: y-részecske
  int id; // sorszám
  int t; // kilövési időpont
  int v; // sebesség
  double x; // pozíció (x-részecskék esetén) or y (y-részecskék esetén)
};

bool compare_by_time(const Particle& p1, const Particle& p2) {
  return p1.t < p2.t;
}

bool compare_by_position(const Particle& p1, const Particle& p2) {
  return p1.x < p2.x;
}

int main() {
  int N, L, K;
  cin >> N >> L >> K;

  vector<Particle> x_particles(N);
  vector<Particle> y_particles(N);

  for (int i = 0; i < N; ++i) {
    cin >> x_particles[i].t >> x_particles[i].v;
    x_particles[i].type = 0;
    x_particles[i].id = i + 1;
  }

  for (int i = 0; i < N; ++i) {
    cin >> y_particles[i].t >> y_particles[i].v;
    y_particles[i].type = 1;
    y_particles[i].id = i + 1;
  }

  sort(x_particles.begin(), x_particles.end(), compare_by_time);
  sort(y_particles.begin(), y_particles.end(), compare_by_time);

  for (int k = 0; k < K; ++k) {
    // Megtaláljuk a legközelebb ütköző x- és y-részecskét
    int x_index = 0;
    int y_index = 0;
    double min_distance = L + 1;

    for (int i = 0; i < N; ++i) {
      const Particle& x_particle = x_particles[i];
      const Particle& y_particle = y_particles[y_index];

      double distance = x_particle.x - y_particle.x;
      if (distance < 0) {
        distance += L;
      }

      if (distance < min_distance) {
        min_distance = distance;
        x_index = i;
      }

      if (y_particle.x >= x_particle.x) {
        ++y_index;
        if (y_index == N) {
          break;
        }
      }
    }

    // Kiírjuk az ütköző részecskék sorszámát
    const Particle& x_particle = x_particles[x_index];
    const Particle& y_particle = y_particles[y_index];
    cout << x_particle.id << " " << y_particle.id << endl;

    // Frissítjük az x- és y-részecskék pozícióját
    for (int i = x_index; i < N; ++i) {
      x_particles[i].x += x_particles[i].v * (L - min_distance);
    }

    for (int i = y_index; i < N; ++i) {
      y_particles[i].x += y_particles[i].v * min_distance;
    }
  }

  return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/100
1Wrong answer0/53ms1816 KiB
2Wrong answer0/53ms2004 KiB
3Wrong answer0/53ms2252 KiB
4Wrong answer0/54ms2476 KiB
5Wrong answer0/54ms2700 KiB
6Wrong answer0/54ms2768 KiB
7Wrong answer0/519ms3752 KiB
8Wrong answer0/528ms4440 KiB
9Wrong answer0/537ms4648 KiB
10Wrong answer0/550ms5436 KiB
11Wrong answer0/561ms6060 KiB
12Wrong answer0/571ms6552 KiB
13Wrong answer0/586ms7000 KiB
14Wrong answer0/593ms7408 KiB
15Wrong answer0/598ms7792 KiB
16Wrong answer0/5108ms8524 KiB
17Wrong answer0/5108ms8588 KiB
18Wrong answer0/5108ms8740 KiB
19Wrong answer0/5108ms8784 KiB
20Wrong answer0/5107ms8888 KiB