QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276826#7015. Rikka with Illuminationsucup-team1209#WA 66ms3568kbC++201.9kb2023-12-06 11:21:362023-12-06 11:21:36

Judging History

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

  • [2023-12-06 11:21:36]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:3568kb
  • [2023-12-06 11:21:36]
  • 提交

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