19722022-12-12 19:01:4212BotiForma-1cpp17Wrong answer 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';
  }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted12ms1904 KiB
subtask20/20
2Wrong answer160ms6900 KiB
3Wrong answer160ms7080 KiB
4Wrong answer160ms7024 KiB
5Wrong answer160ms7332 KiB
6Wrong answer162ms7576 KiB
7Wrong answer160ms7800 KiB
8Wrong answer160ms7748 KiB
9Wrong answer160ms7996 KiB
subtask30/30
10Time limit exceeded2.059s2520 KiB
11Time limit exceeded2.058s2824 KiB
12Time limit exceeded2.082s3604 KiB
13Time limit exceeded2.058s3488 KiB
14Time limit exceeded2.065s3636 KiB
15Time limit exceeded2.081s3688 KiB
16Time limit exceeded2.069s3688 KiB
17Time limit exceeded2.069s3936 KiB
18Time limit exceeded2.056s3876 KiB
subtask40/50
19Time limit exceeded2.069s5604 KiB
20Time limit exceeded2.059s5800 KiB
21Time limit exceeded2.066s5712 KiB
22Time limit exceeded2.026s6024 KiB
23Time limit exceeded2.071s5924 KiB
24Time limit exceeded2.075s5780 KiB
25Time limit exceeded2.059s5804 KiB
26Time limit exceeded2.066s5740 KiB
27Time limit exceeded2.071s5808 KiB
28Time limit exceeded2.066s5724 KiB
29Time limit exceeded2.055s5932 KiB
30Time limit exceeded2.058s6060 KiB