QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #483752 | #6353. Kth Lex Min Min Min Subpalindromes | zdczdc | RE | 38ms | 11692kb | C++14 | 2.6kb | 2024-07-19 11:45:59 | 2024-07-19 11:45:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
}
using ll = long long;
using db = long double;
template <typename T> using vec = vector<T>;
int n, m; ll K;
namespace Task1 {
void solve() {
if(K == 1)
for(int i = 1; i <= n; i++) cout << "1 ";
else cout << "-1";
}
}
namespace Task2 {
void solve() {
const vec<vec<string>> str {
{},
{"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 "}};
if(n <= 6) {
if(K > str[n].size()) cout << "-1";
cout << str[n][K - 1];
}else {
if(K > str[6].size()) cout << "-1";
else {
string k = str[6][K - 1], ans;
while(ans.size() + 12 <= n * 2) ans += k;
ans += k.substr(0, n * 2 - ans.size());
cout << ans << "\n";
}
}
}
}
namespace Task3 {
const int kLim = 1e6 + 5;
const ll inf = 1e18;
array<ll, kLim> val;
void solve() {
val[0] = 1;
for(int i = 1; i <= n; i++) {
int coef = (i + 2 <= n) ? m - 2 : m - (n - i);
db cur = val[i - 1] * 1. * coef;
if(cur > inf) val[i] = inf;
else val[i] = val[i - 1] * coef;
}
if(val[n] < K) return void(cout << "-1");
int x, y;
for(int i = 1; i <= n; i++) {
ll rk = (K - 1) / val[n - i] + 1;
if(i == 1) cout << (x = rk) << " ";
else if(i == 2)
cout << (y = ((rk < x) ? rk : rk + 1)) << " ";
else {
int l = min(x, y), r = max(x, y);
if(rk < l) cout << (x = rk) << " ";
else if(rk < r - 1) cout << (x = rk + 1) << " ";
else cout << (x = rk + 2) << " ";
swap(x, y);
}
K -= val[n - i] * (rk - 1);
}
}
}
int32_t main() {
// file();
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> K;
if(m == 1) return Task1::solve(), 0;
if(m == 2) return Task2::solve(), 0;
return Task3::solve(), 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
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: 3536kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
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: 3584kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 38ms
memory: 11352kb
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: 34ms
memory: 11692kb
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: 3584kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: -100
Runtime Error
input:
3 2 7