QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102338 | #6353. Kth Lex Min Min Min Subpalindromes | Alpha_Q# | WA | 83ms | 11520kb | C++17 | 2.5kb | 2023-05-03 04:56:39 | 2023-05-03 04:56:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const __int128 INF = 1e18 + 69;
int n, m; long long k, power[N];
vector <int> two[] = {{1, 1, 2, 1, 2, 2}, {1, 1, 2, 2, 1, 2}, {1, 2, 1, 1, 2, 2}, {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}, {2, 1, 1, 2, 1, 2}, {2, 1, 1, 2, 2, 1}, {2, 1, 2, 1, 1, 2}, {2, 1, 2, 2, 1, 1}, {2, 2, 1, 1, 2, 1}, {2, 2, 1, 2, 1, 1}};
int main() {
cin >> n >> m >> k;
if (n == 1) {
if (k > m) puts("-1");
else printf("%lld\n", k);
return 0;
}
if (m == 1) {
if (k > 1) {
puts("-1");
} else {
for (int i = 1; i <= n; ++i) printf("1 ");
puts("");
}
return 0;
}
if (n == 2) {
long long total = (long long) m * (m - 1);
if (total < k) {
puts("-1");
} else {
long long A = (k + m - 2) / (m - 1);
k -= (A - 1) * (m - 1);
long long B = k;
if (B >= A) ++B;
printf("%lld %lld\n", A, B);
}
return 0;
}
if (m == 2) {
if (n <= 6) {
vector <vector <int>> who;
for (int i = 0; i < 12; ++i) {
who.emplace_back(two[i].begin(), two[i].begin() + n);
}
who.erase(unique(who.begin(), who.end()), who.end());
if (k > who.size()) {
puts("-1");
} else {
for (int x : who[k - 1]) printf("%d ", x);
puts("");
}
} else {
if (k > 12) {
puts("-1");
} else {
for (int i = 0; i < n; ++i) printf("%d ", two[k - 1][i % 6]);
puts("");
}
}
return 0;
}
if (m == 3) {
if (k > 6) {
puts("-1");
} else {
vector <int> vec({1, 2, 3});
for (int i = 1; i < k; ++i) next_permutation(vec.begin(), vec.end());
for (int i = 0; i < n; ++i) printf("%d ", vec[i % 3]);
puts("");
}
return 0;
}
power[0] = 1;
for (int i = 1; i < N; ++i) {
power[i] = min(INF, (__int128) power[i - 1] * (m - 2));
}
__int128 total = min(INF, (__int128) power[n - 2] * m * (m - 1));
if (total < k) {
puts("-1");
return 0;
}
int last = m + 1, prevLast = m + 1;
for (int i = 1; i <= n; ++i) {
__int128 each = i == 1 ? min(INF, (__int128) power[n - 2] * (m - 1)) : power[n - i];
int cur = (k + each - 1) / each;
k -= (cur - 1) * each;
if (last <= cur) ++cur;
if (prevLast <= cur) ++cur;
printf("%d ", cur);
swap(last, prevLast), last = cur;
}
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3628kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 3ms
memory: 11516kb
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: 11272kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 11404kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 2ms
memory: 11412kb
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: 11228kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: -100
Wrong Answer
time: 83ms
memory: 11520kb
input:
1000000 1000000 1000000000000000000
output:
1 2 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 ...
result:
wrong answer 3rd numbers differ - expected: '3', found: '2'