QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#770294 | #8705. 圣遗物 | cz_yxx | 0 | 0ms | 0kb | C++17 | 3.2kb | 2024-11-21 21:22:56 | 2024-11-21 21:22:57 |
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...