QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#733932	#9574. Strips	rose_DKY^#	WA	21ms	7708kb	C++20	2.2kb	2024-11-10 22:11:23	2024-11-10 22:11:24

Judging History

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

[2024-11-10 22:11:24]
评测

测评结果：WA
用时：21ms
内存：7708kb

查看

[2024-11-10 22:11:23]
提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MAXN 200005
#define endl '\n'
ll a[MAXN], b[MAXN];
ll res[MAXN];
ll funx(ll x, ll n)
{
	ll l = 1, r = n;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (a[mid] <= x) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	
	return l;
}
ll funy(ll x, ll n)
{
	ll l = 1, r = n;
	while (l < r) {
		ll mid = (l + r + 1) >> 1;
		if (a[mid] <= x) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	
	return l;
}
void solve()
{
	ll n, m, k, w;
	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];
	}
	b[0] = 0, b[m + 1] = w + 1;
	
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	
	ll cnt = 0;
	for (int i = 0; i <= m; i++) {
		ll l = b[i], r = b[i + 1];
		ll x = funx(b[i], n);
		ll y = funy(b[i + 1], n);
		
		
		if (x > y) {
			continue;
		}
		
		ll s = 0, id = l;
		vector<ll> fa;
		for (int j = x; j <= y; j++) {
			if (a[j] <= id) {
				continue;
			} 
			s += a[j] - id - 1;
			if (a[j] + k - 1 < r) {
				fa.push_back(a[j]);
				id = a[j] + k - 1;
			} else {
				fa.push_back(a[j]);
				ll ff = a[j] + k - 1 - r + 1;
				if (ff > s) {
					cout << -1 << endl;
					return;
				} else {
					ll id2 = r;
				//	cout << fa.size()  << "we" << endl;
					for (int h = fa.size() - 1; h >= 0; h--) {
						//cout << fa[h] << ' ' << id2 << endl;
						if (fa[h] + k - 1 < id2) {
							break;
						} else {
							ll t = fa[h] + k - 1 - id2 + 1;
							//cout << fa[h] << ' ' << t << ' ' << id2 << endl;
							fa[h] -= t;
							id2 = fa[h];
						}
					}
					for (int h = 0; h < fa.size(); h++) {
						res[++cnt] = fa[h];
					}
					
					fa.clear();
					break;
				}
			}
			
			
			
		}
		for (int h = 0; h < fa.size(); h++) {
			res[++cnt] = fa[h];
		}
		fa.clear();
	}
	
	cout << cnt << endl;
	for (int i = 1; i <= cnt; i++) {
		cout << res[i] << ' ';
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	
	
	return 0;
}
/*
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
 */

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 7708kb

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: 21ms

memory: 5712kb

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:

-1
-1
-1
8
3 9 22 26 31 38 54 65 
-1
6
1 8 12 31 41 47 
-1
-1
-1
-1
-1
7
1 7 24 33 43 48 60 
2
4 31 
4
2 11 20 31 
3
3 16 33 
4
3 25 30 42 
3
3 17 60 
4
1 11 21 33 
-1
-1
-1
2
3 81 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45 
-1
-1
5
5 9 18 29 32 
-1
-1
-1
-1
-1
1
38 
-1
5
14 35 43 87 92 
4
18 28 43 47 
4...

result:

wrong answer Participant didn't find a solution but the jury found one. (test case 1)