QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#445551#8529. Balance of Permutationucup-team3695#TL 0ms17068kbC++202.8kb2024-06-16 03:56:292024-06-16 03:56:30

Judging History

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

  • [2024-06-16 03:56:30]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:17068kb
  • [2024-06-16 03:56:29]
  • 提交

answer

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#include <bits/stdc++.h>
#include <bits/extc++.h> 
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair

int n, b;
lll k;
struct chash { // large odd number for C
    const uint64_t C = ll(4e18 * acos(0)) | 71;
    ll operator()(ll x) const { return __builtin_bswap64(x*C); }
};
__gnu_pbds::gp_hash_table<ll,lll,chash> memo[30][30*30];
// unordered_map<ll,lll,chash> memo[30][30*30];
lll dp(int ind, int balrem, int mask) {
    mask &= ~((2<<ind)-1);
    
    if (balrem < 0) return 0;
    if (ind == n && balrem == 0) return 1;
    else if (ind == n) return 0;

    // int possiblekill = (n-1)*(n-ind);
    // if (balrem > possiblekill) return 0;
    auto itr = memo[ind][balrem].find(mask);
    if (itr != memo[ind][balrem].end()) return itr->second;
    // cerr << ind << ' ' << balrem << ' ' << (bitset<6>)mask << endl;

    lll out = 0;
	int lo = 1 + __builtin_popcount(mask);
    rep(i, ind+1, n) {
        if (mask & (1 << i)) continue;
        // try placing i
        int balused = i-ind;
        out += dp(ind+1, balrem - balused - lo, mask | (1 << i));
    }
    out += dp(ind+1, balrem - (lo - 1), mask) * lo;
    return memo[ind][balrem][mask] = out;
}

int out[30];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> b;
    string s;
    cin >> s;
    for (char c : s) {
        k *= 10;
        k += c-'0';
    }

    // cout << ((ll) dp(0, b, 0)) << endl;
    // cout << ((ll) dp(1, b, 1)) << endl;
    // cout << ((ll) dp(2, b, 3)) << endl;
    // return 0;

    int mask = 0;
    
    rep(ind, 0, n) {
        // cerr << "at ind we have " << ((ll) k) << " remaining w/ "<<(bitset<6>)mask << endl;
        rep(i, 0, n) {
            if (mask & (1 << i)) continue;
            int mask2 = mask | (1 << i);
            int restricted = mask & ~((2<<ind)-1);
            int lo = 1 + __builtin_popcount(restricted);
            int rembal = b;
            out[ind] = i;
            if(i>ind){
                rembal -= (i-ind) + lo;
            }else{
                rembal -= lo-1;
            }
            // cout<<i<<' '<<(ll)dp(ind+1, rembal, mask2)<<endl;
            // cout<<rembal<<endl;
            if (dp(ind+1, rembal, mask2) >= k) {
                // place i here
                cout<<i+1<<' ';
                
                b = rembal;
                mask = mask2;
                break;
            } else {
                k -= dp(ind+1, rembal, mask2);
            }
        }
    }
    cout << endl;


}

詳細信息

Test #1:

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

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: