QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #99709 | #6353. Kth Lex Min Min Min Subpalindromes | whatever# | WA | 71ms | 15172kb | C++17 | 2.0kb | 2023-04-23 15:29:20 | 2023-04-23 15:29:24 |
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) {
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;
if (i > 1) x -= (x > a[i - 1]);
if (i > 2) x -= (x > a[i - 2]);
return x;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
if (m == 1) {
if (k > 1) {
cout << "0\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: 0ms
memory: 3388kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 2ms
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: 2ms
memory: 3384kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3500kb
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: 3492kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 65ms
memory: 15172kb
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: -100
Wrong Answer
time: 71ms
memory: 15044kb
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:
wrong answer 999971st numbers differ - expected: '4', found: '3'