QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657137#7015. Rikka with IlluminationsAshbourneWA 77ms34708kbC++202.0kb2024-10-19 14:15:022024-10-19 14:15:02

Judging History

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

  • [2024-10-19 14:15:02]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:34708kb
  • [2024-10-19 14:15:02]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int> 
using namespace std;
const int N = 1005; 
int vis[N][2 * N];
int len[N][2 * N];
int n, m;
int add(int x, int k){
	return 1 + (x - 1 + k) % n; 
}
int dis(int x0, int x1, int y0, int y1, int x, int y){
	return (y1 - y0) * (x - x0) - (x1 - x0) * (y - y0);
}
void solve(){
	cin >> n >> m;
	// clear()
	for(int i = 1;i <= m; ++ i)
		for(int j = 1; j <= 2 * n + 1; ++ j) vis[i][j] = len[i][j] = 0;
	//
	vector<pii> a(n + 1);
	for(int i = 1; i <= n; ++ i){
		int x, y; cin >> x >> y;
		a[i] = {x, y};
	}
	for(int i = 1; i <= m; ++ i){
		int x, y; cin >> x >> y;
		for(int j = 1; j <= n; ++ j){
			auto [a1, a2] = a[j];
			auto [b1, b2] = a[add(j, 1)];
			auto [c1, c2] = a[add(j, 2)];
			int d1 = dis(a1, b1, a2, b2, x, y) > 0 ? 1 : -1, d2 = dis(a1, b1, a2, b2, c1, c2) > 0 ? 1 : -1;
			if(d1 * d2 < 0) vis[i][j] = vis[i][j + n] = 1; 
		}
	}
	for(int i = 1; i <= m; ++ i){
		for(int j = 2 * n; j >= 1; -- j){
			if(vis[i][j]) len[i][j] = len[i][j + 1] + 1;
			else len[i][j] = 0;
		}
	}
	vector<int> f(2 * n, 0), ker(2 * n, -1);
	for(int j = 1; j <= 2 * n; ++ j){
		for(int i = 1; i <= m; ++ i){
			if(f[j] < len[i][j]){
				f[j] = len[i][j];
				ker[j] = i;
			}
		}
	}
	int ans = 1e14;
	vector<int> nans;
	for(int i = 1; i <= n; ++ i){
		vector<int>rans;
		int l = i, r = i + f[i], cs = 1;
		rans.push_back(ker[i]);
		while(l < r && r < i + n){
			int nr = r, tt;
			for(int j = l + 1; j <= r; ++ j){
				if(nr < j + f[j]){
					nr = j + f[j];
					tt = ker[j];
					// cout << tt << endl;
				}
			}
			l = r;
			r = nr;
			rans.push_back(tt);
			++cs;
		}
		if(r >= i + n) {
			if(ans > cs){
				ans = cs;
				nans = rans;
			}
		}
	}
	// cout << (ans == 1e14? -1: ans) << endl;
	if(ans == 1e14) cout << -1 << endl;
	else{
		cout << ans << endl;
		for(auto x: nans) cout << x << " ";
		cout << endl;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	int T;
	cin >> T;
	while(T--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5624kb

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: 77ms
memory: 34708kb

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 19 5 
-1
4
13 27 3 5 
-1
-1
-1
8
8 15 7 3 14 2 10 11 
4
7 6 8 5 
-1
3
3 2 7 
-1
-1
-1
-1
-1
4
8 2 5 13 
4
13 3 12 7 
4
5 7 1 2 
4
17 48 25 13 
4
13 22 38 2 
5
37 40 14 6 34 
37
88 31 5 40 28 1 59 42 21 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...

result:

wrong output format Expected EOLN