19762022-12-12 19:19:5412BotiForma-1cpp17Hibás válasz 0/1002.085s8300 KiB
#include <algorithm>
#include <iostream>
#include <math.h>

using namespace std;
typedef unsigned long long ull;

#define N_MAX 2000
#define Q_MAX 200000
#define T_MAX 1000000

struct Eq {
  int a, b, c, idx;
};

struct Question {
  int P, T, idx;
};

int N, Q;
Eq eqs[N_MAX];
Question qus[Q_MAX];
int ans[Q_MAX];
int place[N_MAX];
ull position[N_MAX];
ull velocity[N_MAX];

bool cmp(int a, int b) {
  if (position[a] > position[b])
    return true;
  if (position[a] < position[b])
    return false;
  if (eqs[a].idx < eqs[b].idx)
    return true;
  return false;
}

int main() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> eqs[i].a >> eqs[i].b >> eqs[i].c;
    eqs[i].idx = i + 1;
  }
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> qus[i].P >> qus[i].T;
    qus[i].P--;
    qus[i].idx = i;
  }
  sort(qus, qus + Q,
       [](const Question &a, const Question &b) { return a.T < b.T; });

  // a(x+1)^2+b(x+1)+c - (ax^2+bx+c)
  // = 2ax+a+b
  // 2a(x+1)+a+b - (2ax+a+b)
  // = 2a
  for (int i = 0; i < N; i++) {
    place[i] = i;
    position[i] = eqs[i].c;
    velocity[i] = eqs[i].a + eqs[i].b;
  }
  int qi = 0;

  for (int T = 0; T < T_MAX; T++) {
    // for (int i = 0; i < N; i++) {
    //   Eq &e = eqs[i];
    //   ull v = e.a * T * T + e.b * T + e.c;
    //   if (v != position[i]) {
    //     cout << "err " << T << '\n';
    //     cout << v << ' ' << position[i] << '\n';
    //     return 1;
    //   }
    // }

    if (qi < Q && qus[qi].T == T) {
      sort(place, place + N, cmp);
      ans[qus[qi].idx] = eqs[place[qus[qi].P]].idx;
      qi++;
    }
    ull minpos = ~(ull)0;
    for (int i = 0; i < N; i++) {
      position[i] += velocity[i];
      velocity[i] += 2 * eqs[i].a;
      if (position[i] > minpos) {
        minpos = position[i];
      }
    }
    for (int i = 0; i < N; i++) {
      position[i] -= minpos;
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << ans[i] << '\n';
  }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva16ms1912 KiB
subtask20/20
2Hibás válasz93ms6952 KiB
3Hibás válasz93ms7152 KiB
4Hibás válasz93ms7344 KiB
5Hibás válasz93ms7580 KiB
6Hibás válasz93ms7772 KiB
7Hibás válasz93ms7972 KiB
8Hibás válasz93ms8188 KiB
9Hibás válasz93ms8300 KiB
subtask30/30
10Időlimit túllépés2.042s2728 KiB
11Időlimit túllépés2.049s2936 KiB
12Időlimit túllépés2.062s3572 KiB
13Időlimit túllépés2.073s3680 KiB
14Időlimit túllépés2.058s3632 KiB
15Időlimit túllépés2.052s3916 KiB
16Időlimit túllépés2.082s3812 KiB
17Időlimit túllépés2.085s3980 KiB
18Időlimit túllépés2.072s4064 KiB
subtask40/50
19Időlimit túllépés2.036s5716 KiB
20Időlimit túllépés2.046s5816 KiB
21Időlimit túllépés2.059s5748 KiB
22Időlimit túllépés2.058s6012 KiB
23Időlimit túllépés2.066s5952 KiB
24Időlimit túllépés2.053s6020 KiB
25Időlimit túllépés2.046s6048 KiB
26Időlimit túllépés2.069s5944 KiB
27Időlimit túllépés2.062s6124 KiB
28Időlimit túllépés2.032s6128 KiB
29Időlimit túllépés2.049s6188 KiB
30Időlimit túllépés2.058s6248 KiB