QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99714 | #6353. Kth Lex Min Min Min Subpalindromes | whatever# | WA | 713ms | 116772kb | C++17 | 2.1kb | 2023-04-23 15:38:28 | 2023-04-23 15:38:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using i64 = long long;
using i128 = __int128_t;
using pii = pair<i64, i64>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 1000005;
int n, m, a[N], cnt;
i64 k, ways[N];
bool check(int rp) {
if (rp == 2 && n > 2) return true;
int cnt = 0;
rep(lp, max(1, rp - 6), rp - 1) {
bool flag = true;
rep(i, lp, (lp + rp) / 2) flag &= (a[i] == a[lp + rp - i]);
cnt += flag;
if (cnt > (rp > 2)) return false;
}
return true;
}
void dfs(int cur) {
if (cur == n + 1) {
if (++cnt == k) {
rep(i, 1, n) cout << a[i] << " \n"[i == n];
exit(0);
}
return;
}
rep(i, 1, 2) {
a[cur] = i;
if (check(cur)) dfs(cur + 1);
}
}
i64 mul(i64 x, i64 y) {
return min(i128(2e18), i128(x) * y);
}
int get_rank(int i, int x) {
if (x == a[i - 1] || (i > 1 && x == a[i - 2])) return -1;
int res = x;
if (i > 1) res -= (x > a[i - 1]);
if (i > 2) res -= (x > a[i - 2]);
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
if (m == 1) {
if (k > 1) {
cout << "-1\n";
return 0;
}
rep(i, 1, n) cout << 1 << " \n"[i == n];
return 0;
}
if (m == 2) {
dfs(1);
cout << "-1\n";
return 0;
}
ways[0] = 1;
rep(i, 1, n - 2) ways[i] = mul(ways[i - 1], m - 2);
ways[n - 1] = mul(ways[n - 2], m - 1);
ways[n] = mul(ways[n - 1], m);
if (k > ways[n]) {
cout << "-1\n";
return 0;
}
rep(i, 1, n) {
int need = (k + ways[n - i] - 1) / ways[n - i];
a[i] = need;
while (get_rank(i, a[i]) < need) ++a[i];
k -= (need - 1) * ways[n - i];
cout << a[i] << " \n"[i == n];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3376kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3360kb
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: 3520kb
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: 3300kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 57ms
memory: 15160kb
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: 70ms
memory: 15084kb
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: 3500kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3300kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3360kb
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: 3344kb
input:
4 2 3
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3448kb
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: 2ms
memory: 3500kb
input:
5 2 13
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
6 2 5
output:
1 2 2 1 1 2
result:
ok 6 numbers
Test #21:
score: 0
Accepted
time: 207ms
memory: 116772kb
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: 341ms
memory: 116716kb
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: 433ms
memory: 116648kb
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: 713ms
memory: 116612kb
input:
1000000 2 1000000000000000000
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: -100
Wrong Answer
time: 2ms
memory: 3496kb
input:
1 3 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'