QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135883#6400. Game: CelestekyEEccccccWA 2ms9624kbC++142.5kb2023-08-06 14:34:172023-08-06 14:34:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-06 14:34:18]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9624kb
  • [2023-08-06 14:34:17]
  • 提交

answer

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 1000005;

int n;
LL a[N], dl, dr;
int b[N];

namespace Case1
{
	LL f[N], baka[N];

	void solve(void)
	{
		f[n] = 1;
		int cl = n, cr = n, cp = n + 1;
		LL mx_l = LLONG_MIN / 2;
		FF(i, n - 1, 1)
		{
			while (a[cl] - a[i] >= dl)
			{
				MAX(mx_l, f[cl]);
				--cl;
			}
			while (a[cr] - a[i] > dr) --cr;
			if (cr < cp)
			{
				mx_l = LLONG_MIN / 2;
				cp = cl + 1;
				baka[cl] = LLONG_MIN / 2;
				F(i, cl + 1, cr) baka[i] = max(baka[i - 1], f[i]);
			}
			f[i] = max(mx_l, baka[cr]) + 1;
		}
		if (f[1] < 0) cout << "-1\n";
		else
		{
			F(i, 1, f[1]) cout << 1 << ' ';
			cout << '\n';
		}
	}
}

namespace Case2
{
	bitset<10048> to[10048], baka[10048], tmp;
	int ord[10048];

	void solve(void)
	{
		to[n].reset();
		to[n].set(n);
		int cl = n, cr = n, cp = n + 1;
		tmp.reset();
		FF(i, n - 1, 1)
		{
			while (a[cr] - a[i] > dr) --cr;
			while (a[cl] - a[i] >= dl)
			{
				if (cr >= cp) tmp |= to[cl];
				--cl;
			}
			if (cr < cp)
			{
				tmp.reset();
				cp = cl + 1;
				baka[cl].reset();
				F(i, cl + 1, cr) baka[i] = baka[i - 1] | to[i];
			}
			to[i] = tmp | baka[cr];
			to[i].set(i);
		}

		if (!to[1].test(n)) return cout << "-1\n", void();

		iota(ord + 1, ord + n + 1, 1);
		sort(ord + 1, ord + n + 1, [] (int x, int y)
			{ return b[x] > b[y]; });
		set<LL> pos; multiset<int> val;
		pos.insert(1), val.insert(-b[1]);
		pos.insert(n), val.insert(-b[n]);
		F(_, 1, n)
		{
			int i = ord[_];
			if (i == 1 || i == n) continue;
			int prv = *prev(pos.lower_bound(i)), nxt = *pos.upper_bound(i);
			if (to[prv].test(i) && to[i].test(nxt))
			{
				pos.insert(i);
				val.insert(-b[i]);
			}
		}
		for (auto x : val) cout << -x << ' ';
		cout << '\n';
	}
}

void work(void)
{
	cin >> n >> dl >> dr;
	F(i, 1, n) cin >> a[i];
	a[n + 1] = 10000000000LL;
	bool all_1 = true;
	F(i, 1, n)
	{
		cin >> b[i];
		if (b[i] != 1) all_1 = false;
	}
	if (all_1) Case1::solve();
	else Case2::solve();
}

signed main(void)
{
	// freopen("jump.in", "r", stdin);
	// freopen("jump.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	int _; cin >> _;
	while (_--) work();
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9624kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

5 4 3 
-1

result:

wrong answer 1st lines differ - expected: '3', found: '5 4 3 '