QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #100862 | #6353. Kth Lex Min Min Min Subpalindromes | SolitaryDream# | WA | 104ms | 19084kb | C++20 | 1.2kb | 2023-04-28 14:49:37 | 2023-04-28 14:49:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int BND = 1.1e18;
int n, m, k, a[N];
int pwm2[N];
inline int Mul(int x, int y) {
__int128 tmp = x;
tmp *= y;
if (tmp > BND) tmp = BND;
return tmp;
}
inline int Updiv(int x, int y) {
return (x + y - 1) / y;
}
signed main() {
scanf("%lld%lld%lld", &n, &m, &k);
if (n == 1) {
printf("%lld\n", k <= m ? k : -1ll);
return 0;
}
if (m == 1) {
puts("-1");
return 0;
}
pwm2[0] = 1;
for (int i = 1; i < N; ++i) pwm2[i] = Mul(pwm2[i - 1], m - 2);
int all = Mul(Mul(pwm2[n - 2], m), m - 1);
if (all < k) return puts("-1"), 0;
for (int i = 1; i <= n; ++i) {
int oth = (i == 1 ? Mul(pwm2[n - i - 1], m - 1) : pwm2[n - i]);
int cho = Updiv(k, oth);
k -= oth * (cho - 1);
int u = (i > 1 ? a[i - 1] : m + 1), v = (i > 2 ? a[i - 2] : m + 1);
if (u > v) swap(u, v);
if (cho >= u) ++cho;
if (cho >= v) ++cho;
a[i] = cho;
}
for (int i = 1; i <= n; ++i) printf("%lld ", a[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3484kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 3ms
memory: 12332kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 13168kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 3ms
memory: 12444kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 11532kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 6ms
memory: 11828kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 2ms
memory: 13168kb
input:
58 4 864691128455135232
output:
4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4
result:
ok 58 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 13204kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 104ms
memory: 19056kb
input:
1000000 1000000 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #10:
score: 0
Accepted
time: 81ms
memory: 19084kb
input:
1000000 4 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 6ms
memory: 11736kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: -100
Wrong Answer
time: 5ms
memory: 11612kb
input:
3 2 4
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'