QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#738136	#9574. Strips	nnk	WA	32ms	7728kb	C++20	2.5kb	2024-11-12 17:50:28	2024-11-12 17:50:29

Judging History

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

[2024-11-12 17:50:29]
评测

测评结果：WA
用时：32ms
内存：7728kb

查看

[2024-11-12 17:50:28]
提交

answer

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n, m, k, w;
int a[N], b[N];
vector<int> c[N];
int cnt = 0;
int ans[N];
int rans[N];
void slove()
{
	cnt = 0;
	cin >> n >> m >> k >> w;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		c[i].clear();
	}
	c[m + 1].clear();
	int p = 1;
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	for (int i = 1; i <= m; i++) {
		while (a[p] < b[i] && p <= n) {
			c[i].push_back(a[p]);
			p++;
		}

	}
	b[m + 1] = w+1;
	while (a[p] < b[m + 1] && p <= n) {
		c[m + 1].push_back(a[p]);
		p++;
	}


	for (int i = 1; i <= m + 1; i++) {
		int lst = b[i - 1];
		int sum = 0;
		vector<int> red;
		for (auto& x : c[i]) {
			int temp = 0;
			if (!red.empty())
				temp = x - red.back()+1;
			if (sum + temp > k) {
				cnt++;
				int r = red.back();
				int l = r - k + 1;
				if (l <= lst) {
					l = lst + 1;
				}
				lst = l + k - 1;
				if (lst >= b[i]) {
					cout << -1 << endl;
					return;
				}
				ans[cnt] = l;
				rans[cnt] = l + k - 1;
				red.clear();
				sum = 0;
			}
			if (red.empty()) {
				red.push_back(x);
			}
			else {
				red.push_back(x);
				sum += temp;
			}
		}
		if (!red.empty()) {
			cnt++;
			int r = red.back();
			int l = r - k + 1;
			
			if (l <= b[i-1]) {
				l = b[i - 1] + 1;
				r = l + k - 1;
				if (r >= b[i]) {
					cout << -1 << endl;
					return;
				}
			}
			rans[cnt] = r;
			ans[cnt] = l;
			int nr = r, nl = l;
			if (nl <= lst) {
				nl = lst + 1;
				nr = nl + k - 1;
				rans[cnt] = nr;
				ans[cnt] = nl;
				if (nr >= b[i]) {
					nr = b[i] - 1;
					nl = nr - k + 1;
					rans[cnt] = nr;
					ans[cnt] = nl;
					for (int i = cnt - 1; i >= 1; i--) {
						if (nl > rans[i])break;
						rans[i] = nl - 1;
						ans[i] = rans[i] - k + 1;
						nl = ans[i]; nr = rans[i];
						if (ans[i] > rans[i - 1])break;

					}
				}

			}
			if (nl <= b[i-1]) {
				cout << -1 << endl;
				return;
			}
			//lst = l + k - 1;
			//if (lst >= b[i]) {
			//	/*cout << -1 << endl;
			//	return;*/

			//}
			//ans[cnt] = l;
			red.clear();
			sum = 0;
		}
	}
	cout << cnt << endl;
	for (int i = 1; i <= cnt; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
	/*for (int i = 0; i <= cnt; i++) {
		ans[i] = rans[i] = 0;
	}*/
	

	
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		slove();
	}
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 7728kb

input:

4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2

output:

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100

Wrong Answer

time: 32ms

memory: 5656kb

input:

11000
3 8 2 53
32 3 33
35 19 38 20 1 30 10 6
7 10 1 42
3 14 4 36 28 40 22
17 20 12 41 27 7 1 19 13 9
6 6 13 78
55 76 53 32 54 58
62 45 21 4 7 61
8 7 3 68
9 26 54 31 22 3 38 65
34 16 58 47 52 29 53
5 8 4 33
33 5 30 6 15
27 12 9 28 19 2 13 10
6 1 2 48
8 12 48 1 41 31
40
7 6 7 61
20 19 30 52 49 17 40
3...

output:

2
2 32 
7
3 4 14 22 28 36 40 
3
22 46 64 
8
1 7 20 24 30 36 54 63 
3
3 14 30 
6
1 7 11 30 41 47 
4
14 27 34 47 
2
42 65 
2
21 31 
1
9 
1
62 
5
24 33 42 47 60 
2
3 31 
3
11 19 29 
3
2 15 33 
3
25 30 42 
3
2 17 59 
4
1 11 21 32 
2
53 65 
3
49 58 65 
-1
1
78 
4
1 11 15 21 
5
3 7 17 36 48 
2
1 44 
2
7 2...

result:

wrong answer Participant's answer is 2. But jury has a better answer 1. (test case 9)