QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #709758 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team3519# | AC ✓ | 95ms | 60192kb | C++17 | 2.8kb | 2024-11-04 16:40:30 | 2024-11-04 16:40:30 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = int64_t;
using i128 = __int128_t;
void work1(int n, int m, i64 k) {
if (k > 1) std::cout << "-1\n";
else {
for (int i = 1; i <= n; ++i) std::cout << "1 ";
}
}
constexpr int a[][6] =
{
{0, 0, 1, 0, 1, 1},
{0, 0, 1, 1, 0, 1},
{0, 1, 0, 0, 1, 1},
{0, 1, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 1},
{0, 1, 1, 0, 1, 0},
};
void work2(int n, int m, i64 k) {
if (n == 1) {
if (k <= 2) std::cout << k << '\n';
else std::cout << "-1\n";
return;
}
if (n == 2) {
if (k == 1) std::cout << "1 2\n";
else if (k == 2) std::cout << "2 1\n";
else std::cout << "-1\n";
return;
}
std::vector<std::vector<int>> all;
for (int t = 0; t < 6; ++t) {
std::vector<int> x, y;
for (int i = 0; i < n; ++i) {
x.push_back(a[t][i % 6]);
y.push_back(a[t][i % 6] ^ 1);
}
all.push_back(x);
all.push_back(y);
}
std::sort(all.begin(), all.end());
all.resize(std::unique(all.begin(), all.end()) - all.begin());
if (k > all.size()) {
std::cout << "-1\n";
return;
}
for (int i : all[k - 1]) std::cout << i + 1 << ' ';
}
void work3(int n, int m, i64 k) {
if (n == 1) {
if (k > m) {
std::cout << "-1\n";
return;
}
std::cout << k << '\n';
return;
}
constexpr i64 INF = 2e18;
// m * (m - 1) * (m - 2)**(n - 2)
i64 tot = (i64)m * (m - 1);
for (int i = 0; i < n - 2; ++i) {
tot = std::min((i128)tot * (m - 2), (i128)INF);
if (tot == INF) break;
}
if (tot < k) {
std::cout << "-1\n";
return;
}
auto num = [&](int len) -> i64 {
if (m - 2 == 1) return 1;
i64 tot = 1;
for (int i = 0; i < len; ++i) {
tot = std::min((i128)tot * (m - 2), (i128)INF);
if (tot == INF) break;
}
return tot;
};
k -= 1;
i64 first_two = k / num(n - 2);
k %= num(n - 2);
int x = first_two / (m - 1), y = first_two % (m - 1);
if (y >= x) ++y;
std::vector<int> ans{x, y};
auto kth = [&](int x, int y, int k) {
if (x > y) std::swap(x, y);
if (k >= x) ++k;
if (k >= y) ++k;
return k;
};
for (int i = 3; i <= n; ++i) {
i64 v = num(n - i);
ans.push_back(kth(ans[i - 3], ans[i - 2], k / v));
k %= v;
}
for (int i : ans) std::cout << i + 1 << ' ';
}
int main() {
int n, m;
i64 k;
std::cin >> n >> m >> k;
if (m == 1) work1(n, m, k);
else if (m == 2) work2(n, m, k);
else work3(n, m, k);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 0ms
memory: 3564kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 35ms
memory: 8684kb
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: 95ms
memory: 8624kb
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: 0ms
memory: 3540kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 2 10
output:
2 2 1 2
result:
ok 4 number(s): "2 2 1 2"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 2 3
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
5 2 7
output:
2 1 1 2 1
result:
ok 5 number(s): "2 1 1 2 1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 2 13
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
6 2 5
output:
1 2 2 1 1 2
result:
ok 6 numbers
Test #21:
score: 0
Accepted
time: 51ms
memory: 60192kb
input:
1000000 2 3
output:
1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 ...
result:
ok 1000000 numbers
Test #22:
score: 0
Accepted
time: 48ms
memory: 59860kb
input:
1000000 2 5
output:
1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 ...
result:
ok 1000000 numbers
Test #23:
score: 0
Accepted
time: 53ms
memory: 60004kb
input:
1000000 2 7
output:
2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 ...
result:
ok 1000000 numbers
Test #24:
score: 0
Accepted
time: 19ms
memory: 59840kb
input:
1000000 2 1000000000000000000
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 3 2
output:
2
result:
ok 1 number(s): "2"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 3 5
output:
3 1
result:
ok 2 number(s): "3 1"
Test #27:
score: 0
Accepted
time: 31ms
memory: 8772kb
input:
1000000 3 5
output:
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 1 2 ...
result:
ok 1000000 numbers
Test #28:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
1000000 3 7
output:
-1
result:
ok 1 number(s): "-1"
Test #29:
score: 0
Accepted
time: 95ms
memory: 7948kb
input:
1000000 4 211106232532991
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 #30:
score: 0
Accepted
time: 72ms
memory: 7708kb
input:
1000000 5 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 #31:
score: 0
Accepted
time: 43ms
memory: 9272kb
input:
1000000 123123 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 #32:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 1000000 1000000000000000000
output:
1 2 4 9 15 8
result:
ok 6 numbers
Test #33:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 1000000 1000000000000000000
output:
2 7 15 9
result:
ok 4 number(s): "2 7 15 9"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 1000000 999997000002000000
output:
1000000 999999 999998
result:
ok 3 number(s): "1000000 999999 999998"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 1000000 999997000002000001
output:
-1
result:
ok 1 number(s): "-1"