QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276869 | #7015. Rikka with Illuminations | ucup-team1209# | AC ✓ | 878ms | 3564kb | C++20 | 2.0kb | 2023-12-06 12:06:09 | 2023-12-06 12:06:10 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
using u64 = unsigned long long;
const int mod = 1e9 + 7;
using ll = long long;
struct vec2 {
int x, y;
};
vec2 operator - (const vec2 & x, const vec2 & y) {
return {x.x - y.x, x.y - y.y};
}
vec2 operator + (const vec2 & x, const vec2 & y) {
return {x.x + y.x, x.y + y.y};
}
ll operator * (vec2 x, vec2 y) {
return (ll) x.x * y.y - (ll) x.y * y.x;
}
int T;
int n, m;
struct pr { int l, r, id; };
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
for(int i = 0;i < T;++i) {
cin >> n >> m;
std::vector<vec2> a(n);
std::vector<vec2> b(m);
for(auto & [x, y] : a) cin >> x >> y;
for(auto & [x, y] : b) cin >> x >> y;
std::vector<pr> ranges;
int id = 0;
for(vec2 x : b) {
++ id;
int l = 0, r = 0;
for(int j = 1;j < n;++j) {
if((a[j] - x) * (a[l] - x) < 0) l = j;
if((a[j] - x) * (a[r] - x) > 0) r = j;
}
if(l < r) {
ranges.push_back({l, r, id});
ranges.push_back({l + n, r + n, id});
} else {
ranges.push_back({l, r + n, id});
}
}
sort(ranges.begin(), ranges.end(), [](auto l, auto r) { return l.l < r.l; });
int ans = n + 1;
std::vector<int> ids;
for(int i = 0;i < (int) ranges.size();++i) {
static std::vector<int> tmp;
int goal = ranges[i].l + n;
int x = i, j = i + 1;
tmp = {ranges[i].id};
for(;ranges[x].r < goal;) {
int max = x;
for(;j < (int) ranges.size() && ranges[j].l <= ranges[x].r;++j) {
if(ranges[j].r > ranges[max].r) {
max = j;
}
}
if(max == x) {
break;
}
x = max;
tmp.push_back(ranges[x].id);
}
if(ranges[x].r >= goal) {
if(tmp.size() < ans) {
ans = tmp.size();
ids = tmp;
}
}
}
if(ans <= n) {
cout << ans << '\n';
for(int i = 0;i < (int) ids.size();++i) {
cout << ids[i] << " \n"[i + 1 == ids.size()];
}
} else {
cout << -1 << '\n';
}
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
1 3 3 0 0 1 0 0 1 -1 -1 3 -1 -1 3
output:
2 2 1
result:
ok 1 cases.
Test #2:
score: 0
Accepted
time: 61ms
memory: 3564kb
input:
100 13 17 -976 -766 -628 -956 462 -987 967 -997 981 -123 919 115 847 336 692 789 350 908 -558 996 -843 944 -944 400 -974 -476 -41876798 919231678 -375313647 26070145 -288061228 527643156 -93144407 730297 93699145 -260606010 -393321698 -339399089 644245933 784344503 -731740672 525632046 -32141854 114...
output:
2 5 1 -1 -1 -1 -1 3 17 20 14 -1 4 13 27 3 16 -1 -1 -1 8 19 15 7 3 14 2 10 11 4 6 10 5 7 -1 3 3 2 7 -1 -1 -1 -1 -1 4 8 2 10 21 4 13 3 12 7 4 5 7 1 2 4 17 48 25 13 4 41 1 56 2 5 37 40 22 6 34 37 39 90 58 8 70 47 57 64 44 71 83 26 76 38 51 7 20 84 4 9 12 14 32 45 24 78 68 73 67 23 29 11 48 49 85 75 34 ...
result:
ok 100 cases.
Test #3:
score: 0
Accepted
time: 775ms
memory: 3564kb
input:
100 1000 1000 -206566811 272513 -206555115 -2214957 -206550642 -2598812 -206538524 -3429227 -206534118 -3685047 -206497885 -5342748 -206466348 -6447384 -206454728 -6809307 -206416737 -7877319 -206365268 -9126757 -206352649 -9407755 -206350222 -9460834 -206342491 -9627970 -206253359 -11378633 -206140...
output:
-1 106 567 640 460 660 850 722 990 573 214 893 375 711 683 421 276 30 107 95 561 191 564 413 506 118 836 186 822 765 515 499 882 42 818 524 789 443 249 140 451 872 525 422 959 969 147 716 227 543 577 46 194 877 452 980 903 281 178 24 803 612 75 1 957 894 416 895 173 254 970 39 812 380 205 653 912 88...
result:
ok 100 cases.
Test #4:
score: 0
Accepted
time: 878ms
memory: 3536kb
input:
100 1000 1000 -208687104 -518935 -208658071 -3519412 -208647420 -4102540 -208612602 -5599926 -208458791 -9772885 -208145426 -15035235 -207718591 -20088894 -207636408 -20921257 -207598046 -21298548 -207567860 -21590745 -207181177 -25030716 -206899863 -27258453 -206707452 -28681109 -206631693 -2922191...
output:
461 985 29 304 608 501 941 309 656 91 73 712 725 98 245 609 33 81 970 514 593 559 453 882 880 626 357 452 249 455 993 90 956 9 254 197 731 316 854 37 662 340 539 613 927 787 8 664 874 398 142 998 409 670 270 715 136 746 695 668 96 430 217 403 982 436 407 857 373 42 707 631 105 337 822 831 793 502 52...
result:
ok 100 cases.