QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469062#6400. Game: CelesteluanmengleiWA 0ms14072kbC++142.6kb2024-07-09 12:30:322024-07-09 12:30:32

Judging History

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

  • [2024-07-09 12:30:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14072kb
  • [2024-07-09 12:30:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

using i64 = long long;
using u64 = unsigned long long;
void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}
template<typename T, typename L>
bool chkmax(T &x, L y) { if (x < y) return x = y, true; return false; }
template<typename T, typename L>
bool chkmin(T &x, L y) { if (y < x) return x = y, true; return false; }

const int N = 1e6 + 10;
const u64 B = 1313131;
int n, L, R, a[N], b[N];
bool vis[N];
u64 pw[N];

const int SEG_SIZE = N * 40;
u64 hsh[SEG_SIZE];
int rt[N], lc[SEG_SIZE], rc[SEG_SIZE], cnt[SEG_SIZE], tot;

void insert(int &x, int y, int l, int r, int p) {
	x = ++ tot, lc[x] = lc[y], rc[x] = rc[y], hsh[x] = hsh[y] + pw[p], cnt[x] = cnt[y] + 1;
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	p <= mid ? insert(lc[x], lc[y], l, mid, p) : insert(rc[x], rc[y], mid + 1, r, p);
}

bool compare(int x, int y, int l, int r) {
	if (l == r) {
		return cnt[x] > cnt[y];
	}
	int mid = (l + r) >> 1;
	if (hsh[rc[x]] == hsh[rc[y]])
		return compare(lc[x], lc[y], l, mid);
	else
		return compare(rc[x], rc[y], mid + 1, r);
}

void work(int x, int l, int r) {
	if (!x)
		return;
	if (l == r) {
		for (int i = 1; i <= cnt[x]; i ++)
			cout << l << " ";
		return;
	}
	int mid = (l + r) >> 1;
	work(rc[x], mid + 1, r);
	work(lc[x], l, mid);
}

void ___solve() {
	cin >> n >> L >> R;
	pw[0] = 1;
	for (int i = 1; i <= n; i ++)
		pw[i] = pw[i - 1] * B;
	tot = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], rt[i] = 0, vis[i] = 0;
	for (int i = 1; i <= n; i ++)
		cin >> b[i];
	insert(rt[1], rt[0], 1, n, b[1]);
	deque<int> dq;
	for (int i = 2, j = 0; i <= n; i ++) {
		while (j + 1 < i && a[i] - a[j + 1] >= L) {
			j ++;
			if (vis[j])
				continue;
			while (!dq.empty() && compare(rt[j], rt[dq.front()], 1, n))
				dq.pop_front();
			dq.push_front(j);
		}
		while (!dq.empty() && a[i] - a[dq.back()] > R)
			dq.pop_back();
		if (dq.empty()) {
			vis[i] = 1;
		} else {
			insert(rt[i], rt[dq.back()], 1, n, b[i]);
		}
	}
	if (vis[n]) {
		cout << "-1\n";
	} else {
		work(rt[n], 1, n);
		cout << "\n";
	}
}

}
bool edB;
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
	while (tt --)	
		SOL::___solve();
#ifdef CLESIP
	// cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
	// cerr << "Mem: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
#endif
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14072kb

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 '