QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#445216#8529. Balance of Permutationucup-team1134#TL 344ms528080kbC++233.7kb2024-06-16 00:07:562024-06-16 00:07:57

Judging History

你现在查看的是最新测评结果

  • [2024-06-16 00:07:57]
  • 评测
  • 测评结果:TL
  • 用时:344ms
  • 内存:528080kb
  • [2024-06-16 00:07:56]
  • 提交

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

output:


result: