QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #103668 | #6353. Kth Lex Min Min Min Subpalindromes | SEM_PRESSAO_pedroteosousa# | AC ✓ | 100ms | 20956kb | C++23 | 2.3kb | 2023-05-07 06:59:47 | 2023-05-07 06:59:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long INF = 1'000'000'000'000'000'010ll;
void solve1(int n, int m, long long k) {
if (k != 1) {
cout << -1 << endl;
return;
}
while (n--)
cout << "1 ";
cout << endl;
}
void solve2(int n, int m, long long k) {
vector<string> r[] = {
{"1 ", "2 "},
{"1 2 ", "2 1 "},
{"1 1 2 ", "1 2 1 ", "1 2 2 ", "2 1 1 ", "2 1 2 ", "2 2 1 "},
{"1 1 2 1 ", "1 1 2 2 ", "1 2 1 1 ", "1 2 1 2 ", "1 2 2 1 ", "2 1 1 2 ", "2 1 2 1 ", "2 1 2 2 ", "2 2 1 1 ", "2 2 1 2 "},
{"1 1 2 1 2 ", "1 1 2 2 1 ", "1 2 1 1 2 ", "1 2 1 2 2 ", "1 2 2 1 1 ", "1 2 2 1 2 ", "2 1 1 2 1 ", "2 1 1 2 2 ", "2 1 2 1 1 ", "2 1 2 2 1 ", "2 2 1 1 2 ", "2 2 1 2 1 "},
{"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 g = n >= 6 ? 5 : n - 1;
if (k > r[g].size()) {
cout << -1 << endl;
return;
}
string s = r[g][k - 1];
string resp = "";
for (int i = 0; i < 2 * n; i++) {
resp += s[i % s.size()];
}
cout << resp << endl;
}
long long mul(long long a, long long b, bool check = false) {
bool fodeu = a > numeric_limits<long long>::max() / b;
if (fodeu) {
if (check) assert(false);
return INF;
}
return a * b;
}
void solve3(int n, long long m, long long k) {
vector<long long> pot(n);
pot[0] = 1ll;
for (int i = 1; i < n; i++) {
pot[i] = mul(pot[i - 1], m - 2);
}
vector<long long> resp;
int l = m + 1, ll = m + 1;
if (n == 1) {
if (m >= k) {
cout << k << endl;
} else {
cout << -1 << endl;
}
return;
}
long long mx = mul(m, mul(m - 1, pot[n - 2]));
if (mx < k) {
cout << -1 << endl;
return;
}
for (int i = 0; i < n; i++) {
long long x;
if (i == 0) {
x = mul(pot[n - 2], m - 1);
} else {
x = pot[n - i - 1];
}
long long r = (k - 1) / x;
k -= mul(r, x, true);
if (r >= min(l, ll)) r++;
if (r >= max(l, ll)) r++;
swap(l, ll);
l = r;
resp.push_back(r + 1ll);
}
for (auto r: resp)
cout << r << " ";
cout << endl;
}
int main() {
int n, m;
long long k;
cin >> n >> m >> k;
if (m == 1) solve1(n, m, k);
else if (m == 2) solve2(n, m, k);
else solve3(n, m, k);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3420kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3424kb
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: 1ms
memory: 3308kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 78ms
memory: 20956kb
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: 19216kb
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: 2ms
memory: 3360kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3324kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3340kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3356kb
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: 3424kb
input:
4 2 3
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3348kb
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: 1ms
memory: 3348kb
input:
5 2 13
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
6 2 5
output:
1 2 2 1 1 2
result:
ok 6 numbers
Test #21:
score: 0
Accepted
time: 21ms
memory: 8664kb
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: 19ms
memory: 6860kb
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: 18ms
memory: 8136kb
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: 2ms
memory: 3376kb
input:
1000000 2 1000000000000000000
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3316kb
input:
1 3 2
output:
2
result:
ok 1 number(s): "2"
Test #26:
score: 0
Accepted
time: 1ms
memory: 3388kb
input:
2 3 5
output:
3 1
result:
ok 2 number(s): "3 1"
Test #27:
score: 0
Accepted
time: 77ms
memory: 19208kb
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: 2ms
memory: 10760kb
input:
1000000 3 7
output:
-1
result:
ok 1 number(s): "-1"
Test #29:
score: 0
Accepted
time: 74ms
memory: 19192kb
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: 100ms
memory: 19228kb
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: 62ms
memory: 19200kb
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: 2ms
memory: 3348kb
input:
6 1000000 1000000000000000000
output:
1 2 4 9 15 8
result:
ok 6 numbers
Test #33:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
4 1000000 1000000000000000000
output:
2 7 15 9
result:
ok 4 number(s): "2 7 15 9"
Test #34:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
3 1000000 999997000002000000
output:
1000000 999999 999998
result:
ok 3 number(s): "1000000 999999 999998"
Test #35:
score: 0
Accepted
time: 2ms
memory: 3324kb
input:
3 1000000 999997000002000001
output:
-1
result:
ok 1 number(s): "-1"