19212022-12-10 17:34:51KovácsHunorForma-1cpp17Runtime error 0/1002.081s4156 KiB
#include "stdio.h"
#include "stdlib.h"

long long compare(const void* a, const void* b){
    return *(long long*)a-*(long long*)b;
}

void QuickSort(long long* arr, long long* index, long long size){
    long long pivot = 0;
    for (long long i = 1; i < size; i++)
    {
        if(arr[pivot] < arr[i] || (arr[pivot] == arr[i] && index[pivot] > index[i])){
            arr[pivot] ^= arr[pivot+1];
            arr[pivot+1] ^= arr[pivot];
            arr[pivot] ^= arr[pivot+1];

            index[pivot] ^= index[pivot+1];
            index[pivot+1] ^= index[pivot];
            index[pivot] ^= index[pivot+1];
            pivot++;

            if(i != pivot){
                arr[pivot-1] ^= arr[i];
                arr[i] ^= arr[pivot-1];
                arr[pivot-1] ^= arr[i];

                index[pivot-1] ^= index[i];
                index[i] ^= index[pivot-1];
                index[pivot-1] ^= index[i];
            }
        }
    }
    if(pivot > 1)        QuickSort(arr, index, pivot);
    if(pivot < size-2) QuickSort(arr + (pivot+1), index + (pivot+1), size - (pivot+1));
}

long long distance(long long a, long long b, long long c, long long t){
    return t*t*a + t*b + c;
}

int main()
{
    long long n, q;
    scanf("%lld", &n);
    long long* arr = (long long*)malloc(sizeof(long long)*n*3);
    for (long long i = 0; i < n; i++)
    {
        scanf("%lld%lld%lld", arr + i, arr + i + n, arr + i + 2*n);
    }
    scanf("%lld", &q);
    int* sol = (int*)malloc(sizeof(int)*q);
    long long* dis = (long long*)malloc(sizeof(long long)*n);
    long long* index = (long long*)malloc(sizeof(long long)*n);

    for (long long i = 0; i < q; i++)
    {
        long long p, t;
        scanf("%lld%lld", &p, &t);
        for (long long j = 0; j < n; j++)
        {
            index[j] = j+1;
        }
        for (long long j = 0; j < n; j++)
        {
            dis[j] = distance(arr[j], arr[j+n], arr[j+2*n], t);
        }

        QuickSort(dis, index, n);
        sol[i] = (int)index[p-1];
    }
    for (long long i = 0; i < q; i++)
    {
        printf("%d\n", sol[i]);
    }
    free(arr);
    free(sol);
    free(dis);
    return 1;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error3ms1292 KiB
subtask20/20
2Runtime error82ms2912 KiB
3Runtime error86ms3220 KiB
4Runtime error82ms3344 KiB
5Runtime error79ms3420 KiB
6Runtime error83ms3400 KiB
7Runtime error82ms3640 KiB
8Runtime error82ms3756 KiB
9Runtime error81ms3948 KiB
subtask30/30
10Time limit exceeded2.052s3008 KiB
11Time limit exceeded2.015s2808 KiB
12Time limit exceeded2.063s2768 KiB
13Time limit exceeded2.039s3032 KiB
14Time limit exceeded2.052s3388 KiB
15Time limit exceeded2.063s3256 KiB
16Time limit exceeded2.068s2880 KiB
17Time limit exceeded2.063s3404 KiB
18Time limit exceeded2.055s3332 KiB
subtask40/50
19Time limit exceeded2.028s3512 KiB
20Time limit exceeded2.055s3520 KiB
21Time limit exceeded2.079s3440 KiB
22Time limit exceeded2.063s3468 KiB
23Time limit exceeded2.052s3428 KiB
24Time limit exceeded2.072s4020 KiB
25Time limit exceeded2.069s3896 KiB
26Time limit exceeded2.072s3660 KiB
27Time limit exceeded2.049s3868 KiB
28Time limit exceeded2.059s3648 KiB
29Time limit exceeded2.081s4156 KiB
30Time limit exceeded2.061s3952 KiB