QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445216 | #8529. Balance of Permutation | ucup-team1134# | TL | 344ms | 528080kb | C++23 | 3.7kb | 2024-06-16 00:07:56 | 2024-06-16 00:07:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=32,INF=15<<26;
//int128
//https://kopricky.github.io/code/Misc/int128.html
// __int128の入出力
using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
string s;
is >> s;
v = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
}
if (s[0] == '-') { v *= -1; }
return is;
}
ostream& operator<<(ostream& os, const LL& v)
{
if (v == 0) { return (os << "0"); }
LL num = v;
if (v < 0) {
os << '-';
num = -num;
}
string s;
for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
reverse(s.begin(), s.end());
return (os << s);
}
ll dp[MAX][MAX][MAX][MAX*MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
ll N,tar,K;cin>>N>>tar>>K;
vector<int> ans,deta(N);
for(int s=0;s<N;s++){
for(int t=0;t<N;t++){
if(deta[t]) continue;
deta[t]=true;
ans.push_back(t);
ll def=0;
for(int i=0;i<si(ans);i++) def+=abs(i-ans[i]);
if(def>tar){
deta[t]=false;
ans.pop_back();
continue;
}
memset(dp,0,sizeof(dp));
dp[0][0][0][def]=1;
for(int i=0;i<N;i++){
for(int a=0;a<=i;a++){
for(int b=0;b<=i;b++){
for(int k=0;k<=tar;k++){
if(dp[i][a][b][k]==0) continue;
ll ad=dp[i][a][b][k];
if(i<=s){
if(deta[i]){
dp[i+1][a][b][k+a+b]+=ad;
}else{
if(a) dp[i+1][a-1][b][k+a-1+b]+=ad*a;
dp[i+1][a][b+1][k+a+b+1]+=ad;
}
}else{
if(deta[i]){
if(b) dp[i+1][a][b-1][k+a+b-1]+=ad*b;
dp[i+1][a+1][b][k+a+1+b]+=ad;
}else{
dp[i+1][a][b][k+a+b]+=ad;
if(b) dp[i+1][a][b][k+a+b]+=ad*b;
if(a) dp[i+1][a][b][k+a+b]+=ad*a;
if(a&&b) dp[i+1][a-1][b-1][k+a-1+b-1]+=ad*a*b;
dp[i+1][a+1][b+1][k+a+1+b+1]+=ad;
}
}
}
}
}
}
//cout<<s<<" "<<t<<" "<<dp[N][0][0][tar]<<" "<<K<<endl;
if(dp[N][0][0][tar]>=K){
break;
}else{
K-=dp[N][0][0][tar];
deta[t]=false;
ans.pop_back();
}
}
}
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<ans[i]+1;
}
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 344ms
memory: 528080kb
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