QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#697011 | #9483. Maximize Array | gzy | WA | 2ms | 11996kb | C++14 | 1.3kb | 2024-11-01 09:44:20 | 2024-11-01 09:44:21 |
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], c[N][21], s[N], u[N];
ull f[N][21], g[N];
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); m = __lg(n) + 1;
for(i = 1; i <= n; i++) scanf("%d", &s[i]);
for(g[0] = 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 < m; 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 < m; j++) c[i][j] = c[c[i][j-1]][j-1];
for(j = 1; j < m; 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 = m - 1; ~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 < m; j++) c[i][j]= c[to[i]][j];
for(j = 0; j < m; j++) f[i][j] = f[to[i]][j];
}
}
pt(1);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11936kb
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: 0ms
memory: 9896kb
input:
6 1 1 6 4 2 3 5
output:
6 5
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 11996kb
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: 11888kb
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: '