QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#443292#8529. Balance of Permutationucup-team112#AC ✓432ms10512kbC++205.3kb2024-06-15 15:03:462024-06-15 15:03:51

Judging History

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

  • [2024-06-15 15:03:51]
  • 评测
  • 测评结果:AC
  • 用时:432ms
  • 内存:10512kb
  • [2024-06-15 15:03:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif
  std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n;cin>>n;
  ll b;cin>>b;
  using I=__int128_t;
  I k=0;
  {
    string s;cin>>s;
    for(auto c:s){
      k=k*10+c-'0';
    }
  }
  auto calc=[&](vector<int>p)->I {
    //prefixがpのときの数え上げ
    auto dp=make_v(n+1,n+1,b+1,I(0));
    dp[0][0][0]=1;
    p.resize(n,-1);
    vector<int>q(n,-1);
    rep(i,0,n){
      //OUT(p,i);
      if(p[i]!=-1)q[p[i]]=i;
    }
    ll hozl=0,hozr=0;
    //OUT(p,q);
    rep(i,0,n){
      bool no_match=true;
      if(p[i]!=-1&&p[i]<=i)no_match=false;
      if(q[i]!=-1&&q[i]<=i)no_match=false;
      bool soon=(p[i]==i||(p[i]==-1&&q[i]==-1));
      rep(j,0,n+1){
        rep(o,0,b+1){
          if(o+j*2>b)break;
          if(dp[i][j][o]==0)continue;
          if(j<n&&no_match){
            dp[i+1][j+1][o+j*2]+=dp[i][j][o]; //マッチングなし
          }
          if(soon)dp[i+1][j][o+j*2]+=dp[i][j][o]; //即マッチング
          if(p[i]!=i){
            ll lf=0;
            if(p[i]==-1)lf=j-hozr;
            else if(p[i]<i)lf=1;
            if(q[i]==-1||q[i]>i)dp[i+1][j][o+j*2]+=dp[i][j][o]*lf; //index側のみマッチング
            ll rf=0;
            if(q[i]==-1)rf=j-hozl;
            else if(q[i]<i)rf=1;
            //OUT(i,j,o,lf,rf);
            if(p[i]==-1||p[i]>i)dp[i+1][j][o+j*2]+=dp[i][j][o]*rf; //val側マッチング
            if(j>0)dp[i+1][j-1][o+j*2]+=dp[i][j][o]*lf*rf; //両方マッチング
          }
        }
      }
      if(p[i]!=-1){
        if(p[i]>i)hozl++;
        else if(p[i]<i)hozr--;
      }
      if(q[i]!=-1){
        if(q[i]>i)hozr++;
        else if(q[i]<i)hozl--;
      }
      //OUT(hozl,hozr,i,p[i],q[i]);
    }
    //OUT(dp);
    return dp[n][0][b];
  };
  vector<int>ret;
  // OUT(calc(ret));
  // rep(i,0,n){
  //   ret.PB(i);
  //   res+=calc(ret);
  //   OUT(i,res);
  //   ret.pop_back();
  // }
  //OUT(res);exit(0);
  vector<bool>used(n);
  rep(i,0,n){
    vector<int>tmp=ret;
    rep(j,0,n){
      if(used[j])continue;
      tmp.PB(j);
      auto cl=calc(tmp);
      //OUT(tmp,k,cl);
      if(cl>=k){
        ret.PB(j);
        used[j]=true;
        break;
      }
      tmp.pop_back();
      k-=cl;
    }
  }
  for(auto &z:ret)z++;
  debug(ret,ret.size());
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

6 6 6

output:

1 2 6 3 4 5

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 108ms
memory: 7936kb

input:

30 300 3030303030303030303030

output:

1 2 3 4 9 23 20 28 24 16 21 17 27 29 8 26 25 30 19 18 22 12 7 13 6 10 5 15 14 11

result:

ok 30 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

1 0 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

2 0 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

2 2 1

output:

2 1

result:

ok 2 number(s): "2 1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

5 8 3

output:

1 5 4 2 3

result:

ok 5 number(s): "1 5 4 2 3"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

7 20 100

output:

3 6 7 4 1 5 2

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

7 2 6

output:

2 1 3 4 5 6 7

result:

ok 7 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

7 24 1

output:

4 5 6 7 1 2 3

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

7 22 360

output:

7 6 4 3 5 2 1

result:

ok 7 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

7 20 358

output:

5 7 2 4 6 3 1

result:

ok 7 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

10 48 10001

output:

7 5 8 9 6 10 3 4 1 2

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

10 42 10101

output:

3 9 6 8 10 5 7 2 1 4

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 60ms
memory: 6568kb

input:

25 300 1

output:

7 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 8 9 10 11 12 13

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 128ms
memory: 6796kb

input:

25 300 283788388040048639877

output:

25 24 23 22 21 20 19 18 17 16 11 12 13 14 15 10 9 8 7 5 6 4 2 1 3

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 103ms
memory: 6848kb

input:

26 302 105773752969551707419545

output:

19 22 25 13 17 18 23 20 10 26 16 6 5 11 14 12 24 4 3 21 1 15 7 8 2 9

result:

ok 26 numbers

Test #17:

score: 0
Accepted
time: 120ms
memory: 7456kb

input:

27 308 8781128321749037280676555

output:

16 18 17 21 25 6 20 24 22 15 27 5 7 8 2 9 26 13 1 3 14 10 23 19 4 11 12

result:

ok 27 numbers

Test #18:

score: 0
Accepted
time: 91ms
memory: 7632kb

input:

28 304 806517199954337651602356955

output:

12 17 5 16 23 26 25 15 20 2 19 7 22 24 6 13 11 10 28 8 1 21 18 14 27 3 4 9

result:

ok 28 numbers

Test #19:

score: 0
Accepted
time: 127ms
memory: 7900kb

input:

29 322 40281026669581503094652149519

output:

16 21 10 25 17 29 9 28 2 8 26 27 22 4 3 5 18 14 19 1 23 20 15 11 13 7 6 12 24

result:

ok 29 numbers

Test #20:

score: 0
Accepted
time: 216ms
memory: 9712kb

input:

30 400 46479902466857426153849991132

output:

25 19 30 29 9 20 26 21 14 27 28 10 22 11 24 2 7 4 18 17 5 13 12 6 8 1 15 23 16 3

result:

ok 30 numbers

Test #21:

score: 0
Accepted
time: 259ms
memory: 10332kb

input:

30 450 1140008168482799670544355

output:

26 16 17 18 19 20 21 22 23 24 25 27 28 29 30 1 2 3 5 9 4 8 14 10 6 11 12 15 7 13

result:

ok 30 numbers

Test #22:

score: 0
Accepted
time: 20ms
memory: 5692kb

input:

30 150 480087379811286955791425915

output:

7 4 8 5 16 3 1 12 13 11 9 10 15 25 18 17 20 30 28 2 6 14 23 21 24 26 27 22 19 29

result:

ok 30 numbers

Test #23:

score: 0
Accepted
time: 39ms
memory: 5708kb

input:

30 150 480087379811286955791439470

output:

7 4 8 5 16 3 1 12 13 11 9 10 15 25 18 17 20 30 28 2 19 6 22 24 21 23 26 14 29 27

result:

ok 30 numbers

Test #24:

score: 0
Accepted
time: 292ms
memory: 10088kb

input:

30 440 41509275104334759322587324

output:

22 23 20 24 18 30 19 26 21 28 4 29 17 25 27 16 3 1 2 5 8 13 10 15 7 12 9 14 11 6

result:

ok 30 numbers

Test #25:

score: 0
Accepted
time: 311ms
memory: 10220kb

input:

30 450 1140008168482800727111311

output:

26 16 17 18 19 20 21 22 23 24 25 27 28 29 30 1 2 5 7 14 4 15 8 11 3 13 10 9 6 12

result:

ok 30 numbers

Test #26:

score: 0
Accepted
time: 258ms
memory: 9428kb

input:

30 400 52289890275214604423031772929

output:

26 27 29 21 28 16 18 11 2 25 24 23 6 30 20 13 17 10 15 4 9 12 8 22 19 1 5 7 3 14

result:

ok 30 numbers

Test #27:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

30 0 1

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

result:

ok 30 numbers

Test #28:

score: 0
Accepted
time: 224ms
memory: 10248kb

input:

30 450 1

output:

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

result:

ok 30 numbers

Test #29:

score: 0
Accepted
time: 432ms
memory: 10512kb

input:

30 450 1710012252724199424000000

output:

30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

result:

ok 30 numbers

Test #30:

score: 0
Accepted
time: 307ms
memory: 10480kb

input:

30 450 1692383260428073656742269

output:

30 27 26 28 18 29 21 19 25 17 20 16 24 22 23 7 13 4 6 3 5 12 1 15 14 9 11 8 2 10

result:

ok 30 numbers

Test #31:

score: 0
Accepted
time: 219ms
memory: 8104kb

input:

30 302 5918364042599361729860937331200

output:

30 29 28 27 26 25 14 8 9 10 11 12 13 7 15 16 17 18 19 20 21 22 23 24 6 5 4 3 2 1

result:

ok 30 numbers

Test #32:

score: 0
Accepted
time: 116ms
memory: 7208kb

input:

30 254 2256781660157136563723839089600

output:

25 2 3 12 7 16 19 8 22 6 11 17 27 26 10 24 15 21 20 18 28 9 30 23 14 13 5 29 4 1

result:

ok 30 numbers

Test #33:

score: 0
Accepted
time: 344ms
memory: 10456kb

input:

30 448 3131906441000512625049600

output:

23 20 28 18 26 30 19 29 27 22 17 24 21 25 2 13 16 15 14 12 11 10 9 8 7 6 5 4 3 1

result:

ok 30 numbers

Test #34:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

30 2 20

output:

1 2 3 4 5 6 7 8 9 11 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

result:

ok 30 numbers

Test #35:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

30 2 29

output:

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

result:

ok 30 numbers

Extra Test:

score: 0
Extra Test Passed