QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770294#8705. 圣遗物cz_yxx0 0ms0kbC++173.2kb2024-11-21 21:22:562024-11-21 21:22:57

Judging History

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

  • [2024-11-21 21:22:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-21 21:22:56]
  • 提交

answer

// sis puella oier
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
ll read(){
    ll xx = 0, f = 1; char ch = getchar();
    for (;!isdigit(ch); ch = getchar())f = (ch == '-' ? -1 : 1);
    for (; isdigit(ch); ch = getchar())xx = (xx << 3) + (xx << 1) + ch - '0';
    return xx * f;
}
ll rdd(){
    ll xx = 0, f = 1, xx1 = 0; bool fl = false; char ch = getchar();
    for (;!isdigit(ch); ch = getchar())f = (ch == '-' ? -1 : 1);
    for (; isdigit(ch); ch = getchar()){
        if (ch == '.'){fl = true; continue;}
        if (!fl)xx = (xx << 3) + (xx << 1) + ch - '0';
        else xx1 = (xx1 << 3) + (xx1 << 1) + ch - '0';
    }
    return f * (xx * 100 + xx1);
}
const int N = 50010;
struct node{
    ll x, y; int i, j;
}a[15];
bool operator < (node x, node y){
    return x.x == y.x ? x.y < y.y : x.x < y.x;
}
node operator - (node x, node y){
    return node{x.x - y.x, x.y - y.y, x.i, x.j};
}
ll operator * (node x, node y){
    return x.x * y.y - x.y * y.x;
}
int L;
vector <node> ve[N];
vector <node> merge(vector <node> x, vector <node> y){
    vector <node> ret; ret.clear();
    ret.push_back(node{x[0].x + y[0].x, x[0].y + y[0].y, -1, -1});
    int i = 1, j = 1;
    while(i < x.size() || j < y.size()){
        if (j == y.size() || (i < x.size() && x[i] * y[j] < 0))ret.push_back(x[i++]);
        else ret.push_back(y[j++]);
    }
    return ret;
}
vector <node> mg(int l, int r){
    if (l == r)return ve[l];
    int mid = (l + r) >> 1; return merge(mg(l, mid), mg(mid + 1, r));
}
int itans[N], ans[N];
void solve(){
    L = read();
    for (int i = 1, len; i <= L; ++i){
        len = read();
        for (int j = 1; j <= len; ++j)
            a[j].x = rdd(), a[j].y = rdd(), a[j].i = i, a[j].j = j;
        sort(a + 1, a + len + 1);
        ve[i].clear();
        for (int j = 1; j <= len; ++j){
            while(ve[i].size() >= 2){
                int l = ve[i].size(); --l;
                if ((ve[i][l] - ve[i][l - 1]) * (a[j] - ve[i][l]) >= 0)ve[i].pop_back();
                else break;
            }
            ve[i].push_back(a[j]);
        }
        for (int j = (int)ve[i].size() - 1; j > 0; --j)ve[i][j] = ve[i][j] - ve[i][j - 1];
        // for (auto it : ve[i])cout<<it.x<<" "<<it.y<<endl; cout<<endl;
        itans[i] = ve[i][0].j;
    }
    vector <node> tot = mg(1, L);
    // for (auto it : tot)cout<<it.x<<" "<<it.y<<" "<<it.i<<" "<<it.j<<endl;
    int q = read(); ll A, B, x, y, tmp; int id;
    while(q--){
        A = rdd(), B = rdd();
        id = 0, x = tot[0].x, y = tot[0].y, tmp = (A + x) * (B + y), id = 0;
        for (int i = 1; i < tot.size(); ++i){
            x += tot[i].x, y += tot[i].y;
            if ((A + x) * (B + y) > tmp)tmp = (A + x) * (B + y), id = i;
            // cout<<i<<" "<<x<<" "<<y<<" "<<tmp<<endl;
            // cout<<A+x<<" "<<B+y<<endl;
        }
        // cout<<id<<endl;
        for (int i = 1; i <= L; ++i)ans[i] = itans[i];
        for (int i = 1; i <= id; ++i)ans[tot[i].i] = tot[i].j;
        for (int i = 1; i <= L; ++i)printf("%d ", ans[i]); printf("\n");
    }
}
signed main(){
    int tdd = read(), _ = read();
    while(_--)solve();
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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:


result:


Subtask #2:

score: 0
Runtime Error

Test #3:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Runtime Error

Test #6:

score: 0
Runtime Error

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 8 5 4 5 1 4 4 1 2 4 3 2 3 2 4 2 8 6 1 3 1 7 3 6 5 5 6 7 2 1 4 2 6 2 2 8 7 7 2 8 3 8 10 6 2 2 7 8 1 8 2 6 1 8 3 1 2 1 8 3 5 7 1 5 5 2 1 7 8 8 7 6 6 3 5 6 4 10 8 7 2 6 4 7 3 3 4 1 2 7 6 4 1 10 8 6 1 5 5 6 4 9 5 9 2 1 3 3 3 1 4 5 3 2 2 5 8 7 1 7 10 3 1 7 4 9 2 9 8 9 5 4 10 8 5 2 8 4 7 9...

result:


Subtask #4:

score: 0
Runtime Error

Test #12:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Runtime Error

Test #15:

score: 0
Runtime Error

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:


result: