QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445550 | #8529. Balance of Permutation | ucup-team3695# | WA | 6ms | 17132kb | C++20 | 2.8kb | 2024-06-16 03:55:41 | 2024-06-16 03:55:41 |
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;
//rep(i, 0, n) if (mask & (1 << i)) lo++;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 17132kb
input:
6 6 6
output:
1 3 4 5 2 6
result:
wrong answer 2nd numbers differ - expected: '2', found: '3'