QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487192 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team2307# | WA | 0ms | 3880kb | C++14 | 2.3kb | 2024-07-22 17:57:52 | 2024-07-22 17:57:52 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#pragma GCC target("avx,avx2,sse,sse2")
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int get(int msk, int bit) { return (msk>>bit)&1; }
int longest(int n, int msk) {
int ans = 0;
for(int i = 0; i < n; i++) {
int l = 0;
while(i-l >= 0 && i+l < n && get(msk, i-l) == get(msk, i+l)) l++;
l--;
ans = max(ans, 2*l+1);
}
for(int i = 0; i + 1 < n; i++) {
int l = 0;
while(i-l >= 0 && i+1+l < n && get(msk, i-l) == get(msk, i+1+l)) l++;
l--;
ans = max(ans, 2*l+2);
}
return ans;
}
vector<int> cur;
int limit = 4;
void dfs(int pos, uint8_t msk, ll &n, ll &k) {
if(longest(min(pos, 6), msk) > limit) return;
if(pos == n) {
if(k) k--;
else {
for(auto i : cur) cout << 1+i << " ";
exit(0);
}
return;
}
for(int d = 0; d < 2; d++) {
cur.push_back(d);
dfs(pos+1, 2*msk+d, n, k);
cur.pop_back();
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
// for(int n = 1; n <= 25; n++) {
// int x = n, y = 0;
// for(int msk = 0; msk < 1<<n; msk++)
// x = min(x, longest(n, msk));
// for(int msk = 0; msk < 1<<n; msk++)
// y += longest(n, msk) == x;
// cout << n << " : " << x << " " << y << endl;
// }
ll n, m, k;
cin >> n >> m >> k;
if(m == 1) {
if(k > 1) cout << "-1\n";
else for(int i = 0; i < n; i++) cout << "1 ";
return 0;
}
k--;
if(m == 2) {
if(n < 9) {
for(int msk = 0; msk < 1<<n; msk++)
limit = min(limit, longest(n, msk));
}
dfs(0, 0, n, k);
cout << "-1\n";
return 0;
}
const __int128 inf = ll(1e18) + 44;
vector<__int128> suf_ways(n + 1);
suf_ways[0] = 1;
for(int i = 1; i <= n; i++) {
if(i == n) suf_ways[i] = min(suf_ways[i - 1] * m, inf);
else if(i + 1 == n) suf_ways[i] = min(suf_ways[i - 1] * (m - 1), inf);
else suf_ways[i] = min(suf_ways[i - 1] * (m - 2), inf);
}
if(k > suf_ways.back()) {
cout << "-1\n";
return 0;
}
ll p2 = m + 1, p1 = m + 1;
vector<int> ans;
for(int i = 0; i < n; i++) {
ll ord = k / suf_ways[n - 1 - i] + 1;
ll val = ord;
while(val == p1 || val == p2 || (val - (p1<val) - (p2<val)) < ord) val++;
p2 = exchange(p1, val);
ans.push_back(val);
k %= suf_ways[n - 1 - i];
}
for(auto i : ans) cout << i << ' '; cout << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
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: 3648kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
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: -100
Wrong Answer
time: 0ms
memory: 3572kb
input:
58 4 864691128455135233
output:
7 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 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 1st numbers differ - expected: '-1', found: '7'