QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#697004 | #9483. Maximize Array | gzy | WA | 2ms | 9860kb | C++14 | 1.3kb | 2024-11-01 09:38:03 | 2024-11-01 09:38:03 |
Judging History
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'