QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#442874#8529. Balance of Permutationucup-team3646#TL 1ms3772kbC++204.3kb2024-06-15 13:44:072024-06-15 13:44:07

Judging History

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

  • [2024-06-15 13:44:07]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3772kb
  • [2024-06-15 13:44:07]
  • 提交

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;
}

详细

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

output:


result: