QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728024#9574. Stripsucup-team3931#WA 108ms18224kbC++143.3kb2024-11-09 14:23:452024-11-09 14:24:31

Judging History

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

  • [2024-11-09 14:24:31]
  • 评测
  • 测评结果:WA
  • 用时:108ms
  • 内存:18224kb
  • [2024-11-09 14:23:45]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;

ll n, m, K, W, a[maxn], b[maxn], lsh[maxn], tot, c[maxn], d[maxn], f[maxn], g[maxn];

namespace SGT {
	pii a[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = min(a[x << 1], a[x << 1 | 1]);
	}
	
	void build(int rt, int l, int r) {
		if (l == r) {
			a[rt] = mkp(1e18, l);
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int x, ll y) {
		if (l == r) {
			a[rt].fst = y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	pii query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return a[rt];
		}
		int mid = (l + r) >> 1;
		pii res(1e18, 0);
		if (ql <= mid) {
			res = min(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = min(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
}

void solve() {
	scanf("%lld%lld%lld%lld", &n, &m, &K, &W);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld", &b[i]);
	}
	tot = 0;
	lsh[++tot] = 0;
	lsh[++tot] = W;
	for (int i = 1; i <= n; ++i) {
		if (a[i] + K <= W) {
			lsh[++tot] = a[i] + K;
		}
		if (a[i] + K - 1 <= W) {
			lsh[++tot] = a[i] + K - 1;
		}
		lsh[++tot] = a[i];
		if (a[i] - K >= 1) {
			lsh[++tot] = a[i] - K;
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (b[i] + K <= W) {
			lsh[++tot] = b[i] + K;
		}
		lsh[++tot] = b[i];
		lsh[++tot] = b[i] - 1;
		if (b[i] - K >= 1) {
			lsh[++tot] = b[i] - K;
		}
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= tot; ++i) {
		c[i] = d[i] = 0;
	}
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
		++c[a[i]];
	}
	for (int i = 1; i <= m; ++i) {
		b[i] = lower_bound(lsh + 1, lsh + tot + 1, b[i]) - lsh;
		++d[b[i]];
	}
	for (int i = 1; i <= tot; ++i) {
		c[i] += c[i - 1];
		d[i] += d[i - 1];
	}
	SGT::build(1, 1, tot);
	f[1] = 0;
	SGT::update(1, 1, tot, 1, 0);
	ll ans = 1e18, k = -1;
	for (int i = 2; i <= tot; ++i) {
		if (lsh[i] < K) {
			continue;
		}
		int p = upper_bound(lsh + 1, lsh + tot + 1, lsh[i] - K) - lsh - 1;
		if (d[i] > d[p]) {
			continue;
		}
		int l = 1, r = p, q = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (c[p] == c[mid]) {
				q = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		pii t = SGT::query(1, 1, tot, q, p);
		f[i] = t.fst + 1;
		g[i] = t.scd;
		SGT::update(1, 1, tot, i, f[i]);
		if (c[i] == c[tot]) {
			if (f[i] < ans) {
				ans = f[i];
				k = i;
			}
		}
	}
	if (ans > 1e17) {
		puts("-1");
		return;
	}
	printf("%lld\n", ans);
	while (k > 1) {
		printf("%lld ", lsh[k] - K + 1);
		k = g[k];
	}
	putchar('\n');
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

详细

Test #1:

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

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
14 9 6 2 
-1
2
4 1 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 108ms
memory: 18176kb

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

result:

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