QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746858#9574. StripsbhscerWA 40ms5824kbC++172.9kb2024-11-14 15:44:202024-11-14 15:44:22

Judging History

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

  • [2024-11-14 15:44:22]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:5824kb
  • [2024-11-14 15:44:20]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long
#define fadd(a,b,c) for (int a=b;a<=c;a++)
#define fsub(a,b,c) for (int a=b;a>=c;a--)
#define F first
#define S second
#define CYes cout << "Yes\n"
#define CNo cout << "No\n"
#define CYES cout << "YES\n"
#define CNO cout << "NO\n"
#define println(a) cout << (a) << '\n'

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
void fastIO(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
class bhscer {
public:
    template<typename FIRST, typename ...PACK> static void debug(FIRST first, PACK... params) { std::cout<< first <<' '; debug(params...);}
    template<typename T> static void debug(T end) { std::cout << end << std::endl; }
};
const int N = 5e5;
int a[N], b[N];

void solve() {
	int n, m, k, w;
	cin >> n >> m >> k >> w;
	// map<int,bool> red;
	vector<int> all;
	map<int,int> allMp;
	for (int i=1;i<=n;i++) {
		cin >> a[i];
		// red[a[i]] = true;
		all.push_back(a[i]);
	}
	m += 2;
	b[1] = 0;
	b[m] = w+1;
	for (int i=2;i<m;i++) {
		cin >> b[i];
	}
	for (int i=1;i<=m;i++) {
		// red[b[i]] = false;
		all.push_back(b[i]);
	}
	sort(b+1, b+1+m);

	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());

	for (int i=0;i<all.size();i++) {
		allMp[all[i]] = i;
	}

	vector<int> ans;
	bool ok = true;
	for (int i=0;i<all.size()-1;) {

		// this must be a black.
		// find next black.
		int nextBIdx = upper_bound(b+1, b+1+m, all[i]) - b;
		int nextAllIdx = allMp[b[nextBIdx]];

		int wallL = all[i];
		int wallR = all[nextAllIdx];
		// cout << " here has a range: " << wallL << ' ' << wallR << endl;

		int lastCoverTo = 0;
		bool success = true;
		vector<int> ans1;
		for (int j=i+1;j<nextAllIdx;j++) {
			if (lastCoverTo >= all[j]) {
				continue;
			}

			if (all[j] + k-1 < wallR) {
				lastCoverTo = all[j] + k - 1;
				ans1.push_back(all[j]);
				continue;
			}

			// failed to start a cover
			// the final part end

			// cout << "leftly cover failed" << endl;

			success = false;
			break;
		}

		bool successAgain = true;
		if (!success) {
			ans1.clear();
			int preCoverTo = wallR-1 - k + 1;
			if (preCoverTo > wallL) {

				ans1.push_back(preCoverTo);
				for (int j=nextAllIdx-1;j>i;j--) {
					if (preCoverTo <= all[j]) {
						continue;
					}
					if (all[j]-k+1 > wallL) {
						preCoverTo = all[j]- k + 1;
						ans1.push_back(preCoverTo);
						continue;
					}

					successAgain = false;
				}
			} else {
				successAgain = false;
			}
		}

		if (!successAgain) {
			ok = false;
			break;
		}
		for (auto j: ans1) {
			ans.push_back(j);
		}

		i = nextAllIdx;

	}

	if (!ok) {
		cout << -1 << '\n';
		return;
	}
	cout << ans.size() << '\n';
	for (auto i:ans) {
		cout << i << ' ';
	}
	cout << '\n';
}
signed main() {
	fastIO();
	int _ = 1; cin >> _;
	while (_--) {
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 40ms
memory: 5596kb

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
3 32 
7
3 4 14 22 28 36 40 
3
32 48 66 
8
3 9 22 26 31 38 54 65 
3
5 15 30 
-1
-1
2
52 67 
1
27 
1
22 
1
62 
5
24 33 43 48 60 
2
4 31 
3
11 20 31 
3
3 16 33 
3
25 30 42 
3
3 17 60 
-1
2
54 66 
3
50 59 65 
3
50 62 78 
1
81 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45 
2
7 25 
1
4 
4
9 18 32 29 
3
25 27 44...

result:

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