QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#753225#9574. StripsYFffffffWA 32ms3608kbC++231.7kb2024-11-16 11:52:082024-11-16 11:52:09

Judging History

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

  • [2024-11-16 11:52:09]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:3608kb
  • [2024-11-16 11:52:08]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, INF = 1e18, MOD = 1e9 + 7;
typedef pair<int, int> PII;
typedef unsigned long long ull;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int arr[N], brr[N];
bool st[N];
int n, m, k, w;

void solve()
{
	cin >> n >> m >> k >>  w;
	vector<int> red(n), black(m + 2);
	map<PII,vector<int>> mp;
	
	for(int i = 0; i < n; i ++) cin >> red[i];
	for(int i = 1; i <= m; i ++) cin >> black[i];
	black[0] = 0, black[m + 1] = w + 1;
	
	sort(black.begin(), black.end());
	sort(red.begin(),red.end());
	for(int i = 0; i < n; i ++){
		int b = red[i];
		
		int l = 0, r = m + 1;
		while(l < r){
			int mid = (l + r + 1) >> 1;
			if(black[mid] < b) l = mid;
			else r = mid - 1;
		}
		int ml = black[l];
		
		l = 0, r = m + 1;
		while(l < r){
			int mid = (l + r) >> 1;
			if(black[mid] > b) r = mid;
			else l = mid + 1;
		}
		int mr = black[l];
		
		mp[{ml,mr}].push_back(b);
	}
	
	vector<int> ans;
	for(auto [x,y] : mp){
		auto [bl, br] = x;
		int l = bl;
		int cnt = 0;
		vector<PII> vi;
		for(auto c : y){
			if(c > l){
				int d = c - l - 1;
				cnt += d;
				vi.push_back({c, d});
				l = c + k - 1;
			}else continue;
		}
		int len = vi.size();
		if(vi[len - 1].first + k - 1 >= br && cnt < vi[len - 1].first + k - br){
			cout << -1 << "\n";
			return;
		}
		int temp = vi[len - 1].first + k - br;
		for(int i = len - 1; i >= 0; i --){
			ans.push_back(vi[i].first - temp);
			temp -=vi[i].second;
		}
	}
	cout << ans.size() << "\n";
	for(auto x : ans) cout << x << " ";
	cout << "\n";
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T --)	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

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:

4
2 10 7 14 
-1
2
1 5 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 32ms
memory: 3608kb

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
4 33 
7
6 5 16 26 40 39 38 
3
32 48 66 
8
13 10 26 23 31 44 55 66 
3
5 15 30 
6
38 36 34 32 47 45 
4
17 39 32 55 
2
84 73 
1
31 
1
22 
1
62 
5
24 43 41 64 62 
2
16 57 
3
20 12 31 
3
3 18 33 
3
30 29 79 
3
3 28 60 
4
21 11 1 33 
2
66 64 
3
50 60 69 
3
67 57 79 
1
81 
4
4 11 43 40 
5
3 14 36 34 50 
...

result:

wrong answer There is no stripe covering red cell 3 (test case 1)