QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#697004#9483. Maximize ArraygzyWA 2ms9860kbC++141.3kb2024-11-01 09:38:032024-11-01 09:38:03

Judging History

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

  • [2024-11-01 09:38:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9860kb
  • [2024-11-01 09:38:03]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
using ll = long long;
using db = double;
using ull = unsigned long long;
const int N = 3e5 + 7;
const ull b = 1333331;

int i, j, k, n, m, tp, x, y, K, to[N];
int st[N], p[N], g[N], c[N][21], s[N], u[N];
ull f[N][21];

void pt(int x) {
	if(x == n + 1) return;
	if(u[x]) putchar(s[x] + '0'), putchar(' ');
	pt(to[x]);
}

int main() {
	scanf("%d%d", &n, &K);
	for(i = 1; i <= n; i++) scanf("%d", &s[i]);
	g[0] = 1;
	for(i = 1; i < N; i++) g[i] = g[i-1] * b;
	c[n][0] = n + 1, f[n][0] = s[n]; to[n] = n + 1;
	for(i = 1; i < 21; i++) f[n][i] = s[n] * g[1<<i-1], c[n][i] = n + 1;
	u[n] = 1;
	for(i = n - 1; i; i--) {
		u[i] = 1, f[i][0] = s[i]; c[i][0] = i + 1; to[i] = i + 1;
		for(j = 1; j < 21; j++) c[i][j] = c[c[i][j-1]][j-1];
		for(j = 1; j < 21; j++) f[i][j] = f[i][j-1] * g[1<<j-1] + f[c[i][j-1]][j-1];
		if(i + K > n) continue;
		x = i, y = i + K;
		for(j = 20; ~j; j--) if(f[x][j] == f[y][j]) x = c[x][j], y = c[y][j];
		if(f[x][0] < f[y][0]) {
			to[i] = i + K, u[i] = 0;
			for(j = 0; j < 21; j++) c[i][j]	= c[to[i]][j];
			for(j = 0; j < 21; j++) f[i][j] = f[to[i]][j];
		}
	}
	pt(1);
	return 0;
}

详细

Test #1:

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

input:

9 3
1 2 3 4 1 2 3 4 1

output:

1 2 3 4 1 2 3 4 1 

result:

wrong answer 1st words differ - expected: '4', found: '1'