QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#445551 | #8529. Balance of Permutation | ucup-team3695# | TL | 0ms | 17068kb | C++20 | 2.8kb | 2024-06-16 03:56:29 | 2024-06-16 03:56:30 |
Judging History
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