QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#697002#9483. Maximize ArraygzyWA 3ms18384kbC++141.3kb2024-11-01 09:35:462024-11-01 09:35:51

Judging History

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

  • [2024-11-01 09:35:51]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18384kb
  • [2024-11-01 09:35:46]
  • 提交

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], 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: 100
Accepted
time: 0ms
memory: 18020kb

input:

9 3
1 2 3 4 1 2 3 4 1

output:

4 4 1 

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 3ms
memory: 17940kb

input:

6 1
1 6 4 2 3 5

output:

6 5 

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 18160kb

input:

6 5
6 5 4 3 2 1

output:

6 5 4 3 2 1 

result:

ok 6 tokens

Test #4:

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

input:

1392 5
915 798 656 1252 1170 691 1298 205 254 1334 622 1090 1081 617 365 477 362 1306 35 432 744 144 1277 259 80 410 317 983 916 1089 700 1030 135 156 1102 945 1021 63 251 1173 485 1261 1305 219 1190 151 142 288 795 984 1324 417 1235 1295 374 1091 434 596 553 1298 244 1179 115 767 973 315 603 180 10...

output:


result:

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