QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#487210 | #6353. Kth Lex Min Min Min Subpalindromes | ucup-team2307# | WA | 49ms | 22900kb | C++14 | 2.3kb | 2024-07-22 18:15:29 | 2024-07-22 18:15:29 |
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';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3480kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3460kb
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: 3652kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3544kb
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: 3552kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 31ms
memory: 22852kb
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: 49ms
memory: 22900kb
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: 1ms
memory: 3480kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3476kb
input:
3 2 4
output:
2 2 1
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'