QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#455777#8705. 圣遗物marher50 356ms5852kbC++201.6kb2024-06-26 19:40:242024-06-26 19:40:25

Judging History

你现在查看的是最新测评结果

  • [2024-06-26 19:40:25]
  • 评测
  • 测评结果:50
  • 用时:356ms
  • 内存:5852kb
  • [2024-06-26 19:40:24]
  • 提交

answer

#include<bits/stdc++.h>
#define db long double
using namespace std;
const int N=2e5+299;

int T,n,cc,q;

void clear()
{
    cc=0;
}

struct node
{
    db x,y;int id,t;
    
    friend bool operator<(node a,node b)
    {
        return a.x==b.x?a.y<b.y:a.x<b.x;
    }

    friend node operator-(node a,node b)
    {
        return (node){a.x-b.x,a.y-b.y,a.id,a.t};
    }

    friend node operator+(node a,node b)
    {
        return (node){a.x+b.x,a.y+b.y,a.id,a.t};
    }

    db find(db a,db b)
    {
        return (x+a)*(y+b);
    }
}a[N],p[90];

bool cmp(node a,node b)
{
    return a.y*b.x>=b.y*a.x;
}

int chk(node a,node b,node c)
{
    return cmp(c-a,b-a);
}

void add(int pos)
{
    int m;cin>>m;
    for(int i=1;i<=m;i++)cin>>p[i].x>>p[i].y,p[i].id=i,p[i].t=pos;
    p[++m]=(node){0,0,-1,-1};
    sort(p+1,p+1+m);
    int top=1;
    for(int i=2;i<=m;i++)
    {
        while(top>1&&chk(p[top-1],p[top],p[i]))top--;
        p[++top]=p[i];
    }
    for(int i=2;i<=top;i++)a[++cc]=p[i]-p[i-1];
}

int f[N];

void sol()
{
    cin>>n;
    for(int i=1;i<=n;i++)add(i);
    sort(a+1,a+1+cc,cmp);
    cin>>q;
    while(q--)
    {
        db x,y,res=0;int id=0;
        node now=node{0,0};
        cin>>x>>y;
        for(int i=1;i<=cc;i++)
        {
            now=now+a[i];
            if(now.find(x,y)>res)res=now.find(x,y),id=i;
        }
        for(int i=1;i<=id;i++)f[a[i].t]=a[i].id;
        for(int i=1;i<=n;i++)cout<<f[i]<<' ';
        puts("");
    }
}

int main()
{
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    cin>>T>>T;
    while(T--)sol(),clear();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 4ms
memory: 5704kb

input:

1 100
5
3
98 71 28 7 62 13
3
29 23 65 70 34 95
3
59 41 64 43 92 59
3
73 75 99 96 43 2
3
14 24 5 7 54 13
10
8.06 47.73
183.28 351.90
83.70 90.40
34.00 127.83
216.88 312.31
182.09 349.61
266.90 320.28
84.18 420.91
33.26 145.00
118.07 354.22
5
3
25 63 11 75 63 31
3
94 53 38 89 46 23
3
49 99 12 80 52 4
...

output:

1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
1 2 3 2 3 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
3 1 1 2 1 
1 3 1 1 2 
1 3 1 1 2 
1 3 1 1 2 
1 2 1 1 2 
1 2 1 1 2 
1 2 1 1 2 
1 3 1 1 2 
1 3...

result:

ok OK, Accepted

Test #2:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

1 100
5
3
100 44 62 34 64 47
3
9 52 94 73 70 100
3
8 10 87 17 53 61
3
89 88 5 36 2 35
3
76 13 90 71 45 89
10
33.88 69.11
120.74 410.51
119.96 340.70
82.73 416.98
27.98 30.22
69.37 110.99
27.26 153.77
36.29 164.04
56.99 241.65
158.23 272.16
5
3
87 41 60 98 33 50
3
7 83 3 43 78 6
3
88 42 98 97 72 91
3...

output:

1 3 3 1 2 
1 2 3 1 2 
1 2 3 1 2 
1 2 2 1 2 
1 3 3 1 2 
1 3 3 1 2 
1 2 3 1 2 
1 2 3 1 2 
1 2 3 1 2 
1 3 3 1 2 
2 3 2 3 1 
2 3 2 3 1 
2 3 2 3 1 
2 3 2 3 1 
2 3 2 3 1 
2 1 2 3 1 
2 3 2 3 1 
2 1 2 3 1 
2 3 2 3 1 
2 3 2 3 1 
2 3 3 3 3 
2 3 3 3 3 
2 3 3 3 3 
2 3 3 3 3 
2 3 3 3 3 
2 3 3 3 3 
2 3 3 3 3 
2 3...

result:

ok OK, Accepted

Subtask #2:

score: 20
Accepted

Test #3:

score: 20
Accepted
time: 11ms
memory: 3808kb

input:

2 100
27
9
58 21 76 52 99 40 22 25 26 38 25 65 80 47 59 83 12 7
10
87 40 54 90 65 88 86 75 92 22 5 70 53 88 72 34 25 55 7 66
10
8 69 28 19 80 41 17 15 40 82 9 57 77 43 79 63 24 39 62 30
10
38 41 5 45 55 80 93 63 96 46 98 50 31 48 49 49 77 63 46 54
10
99 11 33 21 69 25 9 17 93 30 87 16 22 93 97 36 84...

output:

8 4 8 4 10 10 6 2 6 7 10 6 8 4 10 4 5 6 4 5 9 3 7 7 9 10 2 
3 4 8 4 10 10 6 10 6 7 10 6 8 1 10 4 5 5 4 5 9 3 7 7 9 10 2 
3 4 8 4 10 10 6 10 3 7 10 6 8 1 10 4 5 5 4 5 3 3 7 7 9 5 2 
3 4 8 4 10 10 6 10 3 7 10 6 8 1 10 4 5 5 4 5 3 3 7 7 9 5 2 
3 4 8 4 10 10 6 10 6 7 10 6 8 1 10 4 5 5 4 5 3 3 7 7 9 10 2...

result:

ok OK, Accepted

Test #4:

score: 0
Accepted
time: 11ms
memory: 3832kb

input:

2 100
20
9
87 13 97 57 97 11 92 28 57 82 84 72 56 15 10 21 25 24
9
58 100 94 59 25 87 100 26 47 32 58 46 16 25 65 76 54 65
9
42 3 17 26 44 22 20 83 11 93 7 51 87 7 85 5 96 23
8
26 67 18 14 24 74 8 90 9 90 38 75 33 7 7 40
8
22 25 32 36 95 90 27 2 25 31 82 4 98 77 100 75
8
7 16 94 93 85 100 77 41 90 7...

output:

2 2 9 6 3 2 3 8 1 5 9 3 3 8 3 9 8 5 1 8 
6 1 9 6 3 2 3 8 1 5 9 3 3 8 3 9 7 5 9 8 
2 2 9 6 3 2 3 8 1 5 9 3 3 8 3 9 8 5 9 8 
6 1 9 6 3 2 3 8 1 5 9 3 3 8 3 9 7 5 9 8 
2 2 9 6 3 2 3 8 1 5 9 3 3 8 3 9 8 5 9 8 
2 2 9 6 3 2 3 8 1 5 9 3 3 8 3 9 8 5 9 8 
2 2 9 6 3 2 3 8 1 5 9 3 3 8 3 9 8 5 9 8 
6 1 9 6 3 2 3...

result:

ok OK, Accepted

Test #5:

score: 0
Accepted
time: 11ms
memory: 3664kb

input:

2 100
14
10
60 79 33 78 95 31 45 12 68 96 30 21 66 62 80 43 44 100 20 16
8
25 11 64 47 10 5 39 51 28 12 67 81 86 85 98 22
10
91 99 87 11 61 42 57 87 100 11 4 54 7 50 25 83 16 40 52 38
9
89 100 19 88 4 75 10 15 85 10 98 9 80 38 17 81 48 57
10
62 72 40 10 31 64 79 45 63 10 7 15 78 93 6 69 97 66 71 87
...

output:

5 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 7 2 3 2 5 5 6 7 1 10 
3 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 9 2 3 2 5 5 6 7 1 10 
3 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 9 2 3 2 5 5 6 7 1 10 
3 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 9 2 3 2 5 5 6 7 1 10 
5 7 1 1 9 2 3 2 5 5 6 7 1 10 
...

result:

ok OK, Accepted

Subtask #3:

score: 15
Accepted

Test #6:

score: 15
Accepted
time: 216ms
memory: 3744kb

input:

3 100
496
9
62 33 67 95 25 42 68 17 2 18 65 76 39 78 27 37 55 75
9
97 77 28 91 37 55 83 37 34 82 12 29 58 78 28 6 81 35
8
17 22 2 52 92 14 4 59 82 7 23 37 75 67 39 87
8
62 70 17 5 7 95 84 73 36 35 17 85 84 61 89 69
9
1 80 10 60 37 75 51 64 42 24 89 3 74 56 82 89 87 66
10
79 23 29 19 38 15 14 33 85 1...

output:

2 1 7 8 8 6 3 7 3 6 4 5 1 4 4 1 2 4 3 2 3 2 4 7 8 6 6 3 3 7 1 6 5 2 8 7 2 5 4 2 6 2 2 8 7 9 2 4 4 8 4 6 2 2 7 2 1 3 2 6 7 8 3 1 2 1 8 3 5 7 1 5 5 2 1 7 8 8 7 1 6 3 5 6 4 10 8 7 2 7 4 7 8 3 2 1 2 7 6 4 1 10 7 6 1 5 5 6 4 9 5 9 2 1 3 3 3 1 4 4 3 2 2 5 6 7 1 7 2 3 1 7 4 9 2 9 8 9 5 5 10 8 5 8 4 4 4 9 5...

result:

ok OK, Accepted

Test #7:

score: 0
Accepted
time: 217ms
memory: 3776kb

input:

3 100
495
9
58 39 26 74 43 8 38 40 92 13 39 22 74 72 61 90 96 58
10
75 61 67 30 19 15 10 90 71 21 91 59 42 65 54 6 7 17 95 77
8
78 39 80 44 3 49 56 11 73 75 48 13 70 53 86 85
8
62 50 49 16 35 42 12 2 85 45 38 70 9 7 20 13
9
16 77 12 8 14 83 7 39 89 42 23 74 16 45 4 27 43 100
8
50 67 7 91 60 55 69 51...

output:

9 10 8 5 9 6 4 3 1 5 6 8 1 3 5 8 3 7 6 2 4 4 7 2 8 3 6 4 2 4 4 6 3 7 2 8 2 2 5 9 3 6 7 5 10 1 8 6 6 9 6 2 4 4 3 3 5 5 6 8 1 7 4 6 7 3 9 2 1 1 8 2 1 4 1 7 3 7 4 8 9 9 3 3 10 7 5 8 8 7 8 6 6 7 9 2 4 6 5 4 4 4 8 1 8 8 5 7 2 3 3 6 7 7 7 7 5 8 4 4 4 5 6 5 5 7 8 4 7 6 8 1 2 8 8 6 3 8 2 5 2 8 5 2 7 4 9 9 7...

result:

ok OK, Accepted

Test #8:

score: 0
Accepted
time: 215ms
memory: 5852kb

input:

3 100
482
9
55 66 2 65 79 73 52 98 21 48 64 88 58 25 47 30 13 42
9
86 5 13 53 29 33 98 38 15 79 67 89 16 85 2 66 75 6
10
40 32 76 77 33 64 91 13 50 96 79 36 44 51 17 82 37 13 20 99
10
87 17 38 21 63 23 66 63 33 91 40 90 83 70 73 7 11 38 31 57
8
75 98 42 98 96 28 41 18 80 40 95 24 95 24 94 38
10
54 9...

output:

3 6 2 7 1 2 5 7 4 1 1 4 1 5 7 5 5 3 8 8 7 3 3 7 5 5 2 10 3 8 7 8 7 9 1 4 4 8 8 2 3 5 4 7 5 5 9 10 5 5 8 2 7 3 6 1 8 7 2 7 6 4 1 6 4 8 2 9 7 3 9 8 8 6 8 2 8 2 6 5 2 9 3 9 4 5 4 9 7 9 6 5 7 6 4 2 5 1 4 5 3 5 8 4 9 7 8 10 7 4 2 10 9 7 6 4 8 5 4 6 10 1 3 7 1 8 7 2 6 7 1 6 4 6 1 7 5 1 3 3 8 2 3 9 5 5 2 1...

result:

ok OK, Accepted

Test #9:

score: 0
Accepted
time: 211ms
memory: 3896kb

input:

3 100
492
8
8 78 31 85 67 47 68 5 48 13 50 51 30 63 50 40
9
85 7 55 24 8 62 31 24 25 30 72 41 24 51 13 48 6 46
10
52 46 51 58 5 75 65 72 91 11 87 46 89 60 8 100 50 86 8 90
9
82 37 38 80 72 69 45 14 49 49 67 92 68 56 6 18 1 88
8
38 66 84 1 30 96 40 22 85 83 48 36 48 81 80 34
10
93 31 17 53 26 48 53 8...

output:

3 6 7 6 5 5 1 3 4 1 4 10 3 4 6 8 1 6 10 8 3 9 4 7 2 7 1 3 7 4 1 1 3 3 8 4 4 3 8 2 8 1 1 2 6 5 5 5 7 5 1 9 7 3 3 9 1 1 2 8 4 6 7 9 3 6 9 3 8 10 5 7 8 1 3 10 8 2 3 8 3 3 9 7 2 3 2 1 9 2 1 6 6 1 6 5 5 1 7 2 10 9 5 10 9 2 2 1 8 5 3 3 4 7 6 7 3 7 7 4 8 6 7 7 2 3 10 6 1 4 8 10 6 3 7 1 2 9 8 4 7 1 6 6 7 10...

result:

ok OK, Accepted

Test #10:

score: 0
Accepted
time: 215ms
memory: 3912kb

input:

3 100
486
10
80 39 1 81 76 76 5 65 35 58 61 87 25 45 91 83 79 100 55 92
8
4 29 59 65 76 77 37 3 58 85 63 75 85 67 12 72
9
31 76 66 17 38 45 64 11 94 79 33 1 8 72 59 29 15 56
8
28 28 4 62 80 29 2 40 10 34 60 42 9 36 100 76
10
44 3 25 6 43 53 97 45 71 90 69 51 4 23 70 73 18 100 9 56
9
50 70 32 36 37 8...

output:

9 3 5 8 5 4 10 10 7 6 8 5 4 6 8 7 10 9 9 1 1 2 2 1 1 6 7 3 4 7 3 7 3 4 3 2 7 9 3 5 6 4 1 6 8 1 9 8 7 6 3 3 1 5 5 7 1 6 4 3 9 6 3 2 3 6 7 1 2 6 6 7 9 5 2 1 3 6 6 9 6 2 9 2 6 4 4 1 6 8 5 2 8 7 7 6 7 6 5 4 3 5 6 8 5 3 10 6 5 6 1 8 4 8 8 5 4 7 7 4 1 3 4 3 7 9 9 8 9 10 8 7 8 5 7 4 7 8 8 4 7 9 1 6 8 4 1 9...

result:

ok OK, Accepted

Test #11:

score: 0
Accepted
time: 217ms
memory: 3748kb

input:

3 100
494
8
65 81 55 52 83 29 32 44 61 70 74 33 35 35 28 4
8
21 69 26 6 82 43 20 32 88 54 67 17 15 48 98 54
9
56 16 48 53 47 87 69 79 35 43 67 43 31 82 52 5 67 89
10
86 66 82 73 89 100 48 34 89 54 61 41 91 94 3 75 8 73 10 56
9
7 81 3 37 24 47 82 49 95 15 8 37 46 57 78 25 33 78
9
74 96 40 90 59 60 17...

output:

1 8 9 3 4 8 7 7 9 1 10 1 9 4 7 4 3 7 4 4 9 3 8 8 2 1 6 1 6 4 6 4 3 4 2 1 8 3 3 4 8 9 8 6 4 8 5 1 8 7 7 2 7 7 4 1 6 4 2 3 8 9 3 1 1 3 8 2 5 2 2 6 2 4 2 7 7 3 9 10 8 1 5 8 4 2 10 1 2 4 10 1 5 2 9 1 5 6 6 2 6 2 1 5 4 9 7 4 5 1 5 7 7 2 7 1 4 6 5 7 6 10 8 4 1 4 2 3 6 6 7 7 6 3 8 6 7 4 5 7 2 8 7 8 4 8 2 3...

result:

ok OK, Accepted

Subtask #4:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 356ms
memory: 4164kb

input:

4 100
450
10
30.37 69.63 50.77 49.23 94.68 5.32 36.02 63.98 30.92 69.08 60.25 39.75 94.63 5.37 61.38 38.62 91.27 8.73 28.94 71.06
8
74.79 25.21 8.63 91.37 49.25 50.75 27.02 72.98 72.03 27.97 52.44 47.56 41.20 58.80 44.26 55.74
9
58.02 41.98 35.82 64.18 99.61 0.39 59.26 40.74 47.09 52.91 87.65 12.35 ...

output:

3 1 3 10 4 4 7 8 5 2 10 7 4 2 6 7 1 1 9 6 6 1 4 6 2 7 4 2 2 8 9 7 5 4 7 5 5 7 6 4 5 6 9 5 1 7 7 7 1 4 3 4 8 5 5 3 5 2 2 6 7 4 8 7 4 1 6 4 4 5 8 7 2 7 8 1 8 9 8 5 2 5 9 6 2 5 4 1 5 7 5 5 5 6 2 4 1 4 3 6 5 2 5 3 10 6 1 4 1 3 5 1 1 1 7 7 1 9 9 7 3 4 1 4 1 7 1 2 6 3 2 3 4 5 8 2 3 9 2 2 5 4 5 8 8 5 10 6 ...

result:

wrong answer Test case #1, Query #1, Your answer is not good enough

Subtask #5:

score: 0
Wrong Answer

Test #15:

score: 35
Accepted
time: 319ms
memory: 5748kb

input:

5 100
400
9
1.57 81.69 17.89 66.70 65.51 20.96 14.19 70.10 73.04 13.58 25.01 60.09 57.73 28.55 18.21 66.41 41.57 44.34
8
42.15 15.21 45.93 11.16 27.62 30.65 39.90 17.60 9.87 47.93 51.17 5.44 14.72 43.43 42.11 15.26
9
15.72 52.00 32.33 36.33 7.60 59.51 39.83 28.78 58.75 9.42 30.01 38.51 24.14 44.06 0...

output:

1 5 8 6 3 5 8 5 3 9 1 1 3 5 6 6 1 1 7 3 7 2 3 5 1 4 9 2 7 8 7 4 1 8 8 1 2 7 5 3 2 1 7 8 8 8 1 3 2 1 3 10 8 2 5 3 6 4 3 5 10 3 2 5 1 1 2 8 3 3 5 5 6 1 5 2 2 6 3 1 2 2 7 2 6 3 7 5 3 4 3 3 8 6 7 3 5 9 8 9 6 1 1 5 1 3 2 3 6 2 1 8 7 6 3 6 10 5 5 6 9 8 1 6 7 4 3 3 5 6 2 4 9 6 6 3 9 7 6 1 4 2 2 7 9 2 9 9 3...

result:

ok OK, Accepted

Test #16:

score: -35
Wrong Answer
time: 317ms
memory: 4468kb

input:

5 100
13
10
64.64 5.55 42.82 28.29 14.99 55.69 35.69 35.65 14.18 56.47 55.69 15.01 45.77 25.25 28.49 42.79 55.67 15.04 3.92 66.10
10
30.58 59.22 59.97 28.81 17.77 72.29 23.89 66.09 21.17 68.84 73.61 14.14 47.19 42.19 53.90 35.16 77.27 10.21 1.42 88.79
9
48.23 41.29 26.36 61.91 36.01 52.86 70.58 18.4...

output:

10 10 9 5 9 2 8 8 5 5 1 8 4 
4 4 4 9 8 3 1 9 4 9 5 8 10 
1 9 7 4 7 4 4 1 8 9 3 1 2 
1 9 7 4 7 4 4 1 8 9 3 1 2 
1 9 7 4 7 4 4 1 8 9 3 1 2 
5 10 3 8 4 9 8 8 3 3 1 8 6 
10 10 9 5 9 2 8 8 5 5 1 8 4 
1 9 7 4 7 4 4 1 8 9 3 1 2 
1 9 7 4 7 4 4 1 8 9 3 1 2 
1 9 7 4 7 4 4 1 8 9 3 1 2 
4 7 7 7 8 4 3 6 10 2 6 4...

result:

wrong answer Test case #54, Query #3, Your answer is not good enough