QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442874 | #8529. Balance of Permutation | ucup-team3646# | TL | 1ms | 3772kb | C++20 | 4.3kb | 2024-06-15 13:44:07 | 2024-06-15 13:44:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define elif else if
#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))
struct ScalarInput {
template<class T>
operator T(){
T ret;
cin >> ret;
return ret;
}
};
struct VectorInput {
size_t n;
VectorInput(size_t n): n(n) {}
template<class T>
operator vector<T>(){
vector<T> ret(n);
for(T &x : ret) cin >> x;
return ret;
}
};
ScalarInput input(){ return ScalarInput(); }
VectorInput input(size_t n){ return VectorInput(n); }
template<typename T>
void print(vector<T> a){
for(int i=0;i<a.size();i++){
cout<<a[i]<<" \n"[i+1==a.size()];
}
}
template<class T>
void print(T x){
cout << x << '\n';
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){
cout << head << ' ';
print(forward<Tail>(tail)...);
}
// change min, change max
template<class T>
bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}
template<class T>
bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
using ll = __int128;
// using ll = long long;
int N;
int tmp_mx=0;
ll calc(vector<bool> &P, vector<bool> &Q, int sum, int siz)
{
vector dp(N+1, vector(siz+1, vector(siz+1, vector<ll>(siz*N, 0))));
dp[0][0][0][0] = 1;
int l_cnt=0;
int r_cnt=0;
for (int i = 0; i < N; ++i)
{
int new_tmp_mx=0;
for (int l = 0; l <= l_cnt; ++l)
{
for (int r = 0; r <= r_cnt; ++r)
{
vector<array<int, 3>> vec;
if (P[i] && Q[i])
{
vec.push_back({0, 0, l+r+1});
vec.push_back({-1, -1, l*r});
vec.push_back({1, 1, 1});
}
else if (P[i])
{
vec.push_back({0, -1, r});
vec.push_back({1, 0, 1});
}
else if (Q[i])
{
vec.push_back({-1, 0, l});
vec.push_back({0, 1, 1});
}
else
{
vec.push_back({0, 0, 1});
}
for (int tmp = 0; tmp <= tmp_mx; ++tmp)
{
if (dp[i][l][r][tmp] == 0) continue;
for (auto [dl, dr, w] : vec)
{
int nl = l + dl, nr = r + dr;
if (!(0 <= nl && nl <= siz)) continue;
if (!(0 <= nr && nr <= siz)) continue;
if (!(0 <= tmp + nl + nr && tmp + nl + nr < N * siz)) continue;
dp[i+1][nl][nr][tmp+nl+nr] += w * dp[i][l][r][tmp];
new_tmp_mx=max(new_tmp_mx,tmp+nl+nr);
}
}
}
}
tmp_mx=new_tmp_mx;
if(P[i])l_cnt++;
if(Q[i])r_cnt++;
}
ll ret = dp[N][0][0][sum];
/*
print("calc");
print(P);
print(Q);
print(sum,ret);
cout<<endl;
*/
return ret;
}
void solve()
{
int B; cin >> N >> B;
ll K;
{
string S; cin >> S;
reverse(S.begin(), S.end());
K = 0;
ll mult = 1;
for (auto c : S)
{
K += (c - '0') * mult;
mult *= 10;
}
}
vector<int> ans(N, -1);
vector<bool> used(N, false);
for (int a = 0; a < N; ++a)
{
int realn = 0;
vector<ll> cum(N+1, 0);
for (int n = 0; n < N; ++n)
{
cum[n+1] = cum[n];
if (used[n]) continue;
vector<bool> P(N, false), Q(N, false);
for (int i = 0; i < N; ++i)
{
if (!used[i] && i != n) P[i] = true;
if (i > a) Q[i] = true;
}
// atode
if (B - abs(n - a) < 0) continue;
ll ret = calc(P, Q, B - abs(n - a), N-a);
cum[n+1] += ret;
realn = n;
if (cum[n+1] >= K) break;
}
ans[a] = realn;
used[realn] = true;
K -= cum[realn];
B -= abs(a - realn);
// print(cum);
// cout << a << " " << realn << " " << B << endl;
}
for (int i = 0; i < N; ++i)
{
cout << ans[i] + 1 << " ";
}
cout << endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3772kb
input:
6 6 6
output:
1 2 6 3 4 5
result:
ok 6 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
30 300 3030303030303030303030