#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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 12ms | 1904 KiB | ||||
subtask2 | 0/20 | ||||||
2 | Hibás válasz | 160ms | 6900 KiB | ||||
3 | Hibás válasz | 160ms | 7080 KiB | ||||
4 | Hibás válasz | 160ms | 7024 KiB | ||||
5 | Hibás válasz | 160ms | 7332 KiB | ||||
6 | Hibás válasz | 162ms | 7576 KiB | ||||
7 | Hibás válasz | 160ms | 7800 KiB | ||||
8 | Hibás válasz | 160ms | 7748 KiB | ||||
9 | Hibás válasz | 160ms | 7996 KiB | ||||
subtask3 | 0/30 | ||||||
10 | Időlimit túllépés | 2.059s | 2520 KiB | ||||
11 | Időlimit túllépés | 2.058s | 2824 KiB | ||||
12 | Időlimit túllépés | 2.082s | 3604 KiB | ||||
13 | Időlimit túllépés | 2.058s | 3488 KiB | ||||
14 | Időlimit túllépés | 2.065s | 3636 KiB | ||||
15 | Időlimit túllépés | 2.081s | 3688 KiB | ||||
16 | Időlimit túllépés | 2.069s | 3688 KiB | ||||
17 | Időlimit túllépés | 2.069s | 3936 KiB | ||||
18 | Időlimit túllépés | 2.056s | 3876 KiB | ||||
subtask4 | 0/50 | ||||||
19 | Időlimit túllépés | 2.069s | 5604 KiB | ||||
20 | Időlimit túllépés | 2.059s | 5800 KiB | ||||
21 | Időlimit túllépés | 2.066s | 5712 KiB | ||||
22 | Időlimit túllépés | 2.026s | 6024 KiB | ||||
23 | Időlimit túllépés | 2.071s | 5924 KiB | ||||
24 | Időlimit túllépés | 2.075s | 5780 KiB | ||||
25 | Időlimit túllépés | 2.059s | 5804 KiB | ||||
26 | Időlimit túllépés | 2.066s | 5740 KiB | ||||
27 | Időlimit túllépés | 2.071s | 5808 KiB | ||||
28 | Időlimit túllépés | 2.066s | 5724 KiB | ||||
29 | Időlimit túllépés | 2.055s | 5932 KiB | ||||
30 | Időlimit túllépés | 2.058s | 6060 KiB |