QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276826 | #7015. Rikka with Illuminations | ucup-team1209# | WA | 66ms | 3568kb | C++20 | 1.9kb | 2023-12-06 11:21:36 | 2023-12-06 11:21:36 |
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 x : ids) {
cout << x << ' ';
}
cout << '\n';
} else {
cout << -1 << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3440kb
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: -100
Wrong Answer
time: 66ms
memory: 3568kb
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 ...
result:
wrong output format Expected EOLN