QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276869#7015. Rikka with Illuminationsucup-team1209#AC ✓878ms3564kbC++202.0kb2023-12-06 12:06:092023-12-06 12:06:10

Judging History

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

  • [2023-12-06 12:06:10]
  • 评测
  • 测评结果:AC
  • 用时:878ms
  • 内存:3564kb
  • [2023-12-06 12:06:09]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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.