QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696995#9483. Maximize ArraygzyWA 3ms16140kbC++141.2kb2024-11-01 09:31:312024-11-01 09:31:31

Judging History

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

  • [2024-11-01 09:31:31]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16140kb
  • [2024-11-01 09:31:31]
  • 提交

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 = 1048576 + 7;
const int b = 133331;

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

void pt(int x) {
	if(x == n + 1) return;
	if(to[x] == x + 1) 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;
	for(i = n - 1; i; i--) {
		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;
			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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 16112kb

input:

9 3
1 2 3 4 1 2 3 4 1

output:

4 4 1 

result:

ok 3 tokens

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 16140kb

input:

6 1
1 6 4 2 3 5

output:

1 6 4 2 3 5 

result:

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