QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103595 | #6353. Kth Lex Min Min Min Subpalindromes | gapinho# | WA | 151ms | 239068kb | C++14 | 3.3kb | 2023-05-07 00:10:47 | 2023-05-07 00:10:49 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int ms = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int fat[ms], ifat[ms];
int fexp(int a, int b) {
int ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int c(int a, int b) {
if(b > a) {
return 0;
}
return fat[a] * ifat[a - b] % mod * ifat[b] % mod;
}
int n, m, k;
int szz;
int cnt(string s) {
int ans = 0;
for(int i = 0; i < szz; i++) {
for(int j = i+1; j < szz; j++) {
string k = s.substr(i, j-i+1);
int sz = k.size();
int isp = 1;
for(int a = 0; a < sz; a++) {
if(k[a] != k[sz-a-1]) isp = 0;
}
if(isp) ans++;
}
}
return ans;
}
vector<vector<int>> pos;
void rec(string &now) {
if(now.size() == szz) {
int x = cnt(now);
if(x == szz - 2) {
vector<int> cur;
for(int i = 0; i < szz; i++) {
cur.push_back(now[i] - '0' + 1);
}
pos.push_back(cur);
}
return;
}
for(char i = '0'; i <= '1'; ++i) {
now.push_back(i);
rec(now);
now.pop_back();
}
}
int pot[ms];
vector<int> ans;
void solve(int p, int k, vector<int> proibido) {
if(p == n) {
for(auto v : ans) {
cout << v << ' ';
}
cout << endl;
exit(0);
}
__int128_t sum;
if(p == 0) {
sum = (m - 1);
if(n - p - 2 >= 0) {
sum *= pot[n - p - 2];
} else {
sum = 1;
}
} else {
sum = pot[n - p - 1];
}
int z = k / sum;
int hlp = 0;
vector<int> gamb = proibido;
sort(gamb.begin(), gamb.end());
// cout << "quero: " << z << endl;
// cout << "proibidos: ";
for(auto x : gamb) {
if(x <= z + 1) {
z++;
}
}
// cout << "usando " << z << endl;
if(z >= m) {
cout << -1 << endl;
exit(0);
}
ans.push_back(z + 1);
if(proibido.size() == 2) {
swap(proibido[0], proibido[1]);
proibido.pop_back();
}
proibido.push_back(z + 1);
solve(p + 1, k % sum, proibido);
}
int32_t main() {
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m >> k;
// cin >> n;
pot[0] = 1;
for(int i = 1; i <= n; ++i) {
__int128_t hlp = pot[i - 1];
hlp *= (m - 2);
if(hlp >= inf) {
hlp = inf;
}
pot[i] = hlp;
}
string s;
if(m == 1) {
if(k == 1) {
for(int i = 0; i < n; ++i) {
cout << 1 << ' ';
}
cout << endl;
} else {
cout << -1 << endl;
}
return 0;
}
if(m == 2) {
szz = min(n, 6ll);
string s;
rec(s);
if(k > pos.size()) {
cout << -1 << endl;
return 0;
}
for(int j = 0; j < n; ++j) {
cout << pos[k - 1][j % pos[k - 1].size()] << ' ';
}
cout << endl;
return 0;
}
solve(0, k-1, {});
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5396kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5484kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 5400kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5412kb
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: 5480kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5408kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 2ms
memory: 5504kb
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: 5492kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 151ms
memory: 239068kb
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: 143ms
memory: 238688kb
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: 2ms
memory: 5380kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: -100
Wrong Answer
time: 2ms
memory: 5496kb
input:
1 2 2
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'