19722022-12-12 19:01:4212BotiForma-1cpp17Hibás válasz 0/1002.082s7996 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 >> 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++) {
    if (qi < Q && qus[qi].T == T) {
      sort(place, place + N, cmp);
      ans[qus[qi].idx] = eqs[place[qus[qi].P]].idx;
      qi++;
    }
    for (int i = 0; i < N; i++) {
      position[i] += velocity[i];
      velocity[i] += 2 * eqs[i].a;
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << ans[i] << '\n';
  }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms1904 KiB
subtask20/20
2Hibás válasz160ms6900 KiB
3Hibás válasz160ms7080 KiB
4Hibás válasz160ms7024 KiB
5Hibás válasz160ms7332 KiB
6Hibás válasz162ms7576 KiB
7Hibás válasz160ms7800 KiB
8Hibás válasz160ms7748 KiB
9Hibás válasz160ms7996 KiB
subtask30/30
10Időlimit túllépés2.059s2520 KiB
11Időlimit túllépés2.058s2824 KiB
12Időlimit túllépés2.082s3604 KiB
13Időlimit túllépés2.058s3488 KiB
14Időlimit túllépés2.065s3636 KiB
15Időlimit túllépés2.081s3688 KiB
16Időlimit túllépés2.069s3688 KiB
17Időlimit túllépés2.069s3936 KiB
18Időlimit túllépés2.056s3876 KiB
subtask40/50
19Időlimit túllépés2.069s5604 KiB
20Időlimit túllépés2.059s5800 KiB
21Időlimit túllépés2.066s5712 KiB
22Időlimit túllépés2.026s6024 KiB
23Időlimit túllépés2.071s5924 KiB
24Időlimit túllépés2.075s5780 KiB
25Időlimit túllépés2.059s5804 KiB
26Időlimit túllépés2.066s5740 KiB
27Időlimit túllépés2.071s5808 KiB
28Időlimit túllépés2.066s5724 KiB
29Időlimit túllépés2.055s5932 KiB
30Időlimit túllépés2.058s6060 KiB