QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125074 | #6353. Kth Lex Min Min Min Subpalindromes | tiom4eg | RE | 1ms | 3592kb | C++14 | 5.5kb | 2023-07-16 00:51:05 | 2023-07-16 00:51:06 |
Judging History
answer
#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define vi vector <int>
#define mi vector <vector <int>>
// Quick functions
#define endl '\n'
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define pb push_back
#define mp make_pair
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORS(i, a, b, c) for (int i = a; i < b; i += c)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
#define EACH(e, a) for (auto& e : a)
// Pragmas
#ifndef TIOM4EG
#pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
#pragma GCC target("avx,avx2,popcnt,tune=native")
#pragma GCC comment(linker, "/stack:200000000")
#endif
// PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
#define int long long
constexpr int INF = 0x3f3f3f3f, MD = 998244353, MAX = 300030, LG = 19, MOD = 1e9 + 7, B = 40, P = 31, R = 1 << LG;
const ll INFLL = 1e18 + 7, MOD2 = MOD * MOD;
const string Z[] = {"112122", "112212", "121122", "121221", "122112", "122121", "211212", "211221", "212112", "212211", "221121", "221211"};
int count_pals(string s) {
int n = sz(s);
vector<int> d1(n);
int l=0, r=-1;
for (int i=0; i<n; ++i) {
int k = i>r ? 1 : min (d1[l+r-i], r-i+1);
while (i+k < n && i-k >= 0 && s[i+k] == s[i-k]) ++k;
d1[i] = k;
if (i+k-1 > r) l = i-k+1, r = i+k-1;
}
vector<int> d2(n);
l=0, r=-1;
for (int i=0; i<n; ++i) {
int k = i>r ? 0 : min (d2[l+r-i+1], r-i+1);
while (i+k < n && i-k-1 >= 0 && s[i+k] == s[i-k-1]) ++k;
d2[i] = k;
if (i+k-1 > r) l = i-k, r = i+k-1;
}
int o = 0; FOR(i, 0, n) o += d1[i] + d2[i];
return o;
}
int n, m, k;
vector <string> lol;
void rec(string s, int p) {
if (p == n) return void(lol.pb(s));
rec(s + '1', p + 1), rec(s + '2', p + 1);
}
signed main() {
fastIO;
cin >> n >> m >> k;
if (n == 1) {
if (k > m) return !(cout << -1);
return !(cout << k);
}
if (m == 1) {
if (k == 1) FOR(i, 0, n) cout << "1 ";
else cout << -1;
return 0;
}
if (m == 3) {
if (k > 6) cout << -1;
else {
if (k == 1) FOR(i, 0, n) cout << "123"[i % 3] << ' ';
if (k == 2) FOR(i, 0, n) cout << "132"[i % 3] << ' ';
if (k == 3) FOR(i, 0, n) cout << "213"[i % 3] << ' ';
if (k == 4) FOR(i, 0, n) cout << "231"[i % 3] << ' ';
if (k == 5) FOR(i, 0, n) cout << "312"[i % 3] << ' ';
if (k == 6) FOR(i, 0, n) cout << "321"[i % 3] << ' ';
}
return 0;
}
if (m == 2) {
if (n > 12) {
if (k > 12) return !(cout << -1);
FOR(i, 0, n) cout << Z[k - 1][i % 6] << ' ';
}
else {
rec("", 0);
int mnp = INF;
EACH(s, lol) mnp = min(mnp, count_pals(s));
int c = 0;
EACH(s, lol) {
if (count_pals(s) == mnp) {
if (++c == k) {
EACH(c, s) cout << c << ' ';
return 0;
}
}
}
cout << -1;
}
return 0;
}
// m >= 4
// check if poss
__int128 tot = m * (m - 1);
FOR(i, 2, n) {
if (k <= tot) break;
tot *= m - 2;
}
if (k > tot) return !(cout << -1);
//
vi ans(n), deg;
// obtain degs of m-2
deg.pb(1);
__int128 cur = m - 2;
while (cur <= k) {
deg.pb(cur);
cur *= m - 2;
}
k -= 1;
// 1st elem
if (n - 2 > sz(deg)) ans[0] = 1;
else {
__int128 cur = deg[n - 2];
cur *= m - 1;
if (cur > k) ans[0] = 1;
else {
int d = k / cur;
ans[0] = d + 1, k -= d * cur;
}
}
pbds cum;
FOR(i, 1, m + 1) cum.insert(i);
cum.erase(ans[0]);
// 2nd elem
if (n - 2 > sz(deg)) {
auto it = cum.begin();
ans[1] = *it, cum.erase(it);
}
else {
__int128 cur = deg[n - 2];
if (cur > k) {
auto it = cum.begin();
ans[1] = *it, cum.erase(it);
}
else {
int d = k / cur;
auto it = cum.find_by_order(d);
ans[1] = *it, k -= d * cur, cum.erase(it);
}
}
// other
FOR(i, 2, n) {
if (n - i - 1 > sz(deg)) ans[i] = 1;
else {
__int128 cur = deg[n - i - 1];
if (cur > k) {
auto it = cum.begin();
ans[i] = *it, cum.erase(it);
}
else {
int d = k / cur;
auto it = cum.find_by_order(d);
ans[i] = *it, k -= d * cur, cum.erase(it);
}
}
cum.insert(ans[i - 2]);
}
EACH(e, ans) cout << e << ' ';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3424kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
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: 3448kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3524kb
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: 1ms
memory: 3484kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: -100
Runtime Error
input:
1000000 1000000 1000000000000000000