QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639265 | #8529. Balance of Permutation | ucup-team134 | ML | 0ms | 20064kb | C++17 | 5.8kb | 2024-10-13 18:37:31 | 2024-10-13 18:37:41 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128
using namespace std;
mt19937 rng(time(NULL));
const int N=30,G=15,M=1<<G;
li top[M][2][G*G+1];
int n,b;
li total[G+1][G*G+1];
li cnt[M][G*G+1];
bool done[M];
void calctop(){
top[M-1][0][0]=1; // basecase
for(int e=0;e<=G;e++){
int my=e&1,other=my^1;
for(int i=0;i<M;i++)for(int j=0;j<G*G;j++)top[i][other][j]=0;
for(int msk=M-1;msk>=0;msk--){
int x=__builtin_popcount(msk);
int nema=G-x + e;
int sledeci=G-nema-1;
for(int uzeto=0;uzeto<=G*G;uzeto++){
if(top[msk][my][uzeto]==0)continue;
bitset<G> aa=msk;
//cout << aa << " " << e << " " << uzeto << ": " << (int)top[msk][my][uzeto] << endl;
if(nema==G){
int myu=uzeto;
for(int i=0;i<G;i++){
if(msk&(1<<i)){
myu+=i;
}
}
//cout << aa << " ";
//printf("%i %i += %i\n",e,myu,(int)top[msk][my][uzeto]);
if(myu>G*G)printf("%i %i\n",myu,G*G);
assert(myu<=G*G);
total[e][myu]+=top[msk][my][uzeto];
assert(cnt[msk][myu]==0);
cnt[msk][myu]+=top[msk][my][uzeto];
continue;
}
// Take it
for(int i=0;i<G;i++){
int ad=abs(i-sledeci);
if(msk&(1<<i)){
assert(ad+uzeto<=G*G);
top[msk^(1<<i)][my][uzeto+ad]+=top[msk][my][uzeto];
}
}
// Take some smaller 1
int ad=sledeci+1;
assert(ad+uzeto<=G*G);
top[msk][other][uzeto+ad]+=top[msk][my][uzeto];
}
}
}
}
vector<int> tk;
void remove(int i){
tk.clear();
for(int msk=0;msk<M;msk++){
if(!(msk&(1<<i))){
if(!done[msk]){
done[msk]=1;
tk.pb(msk);
int em=__builtin_popcount(msk);
for(int k=0;k<=G*G;k++){
//printf("%i %i -= %i\n",em,k,(int)cnt[msk][k]);
total[em][k]-=cnt[msk][k];
}
}
}
}
}
void undo(){
for(auto msk:tk){
done[msk]=0;
int em=__builtin_popcount(msk);
for(int k=0;k<=G*G;k++){
total[em][k]+=cnt[msk][k];
}
}
}
set<int> havebot,havetop;
const int G2=N-G,M2=(1<<G2);
vector<li> bot[M2][G2+1];
int K;
vector<int> mybot;
void reset(){
K=sz(mybot);
for(int i=0;i<(1<<K);i++)for(int j=0;j<=K;j++)bot[i][j].clear();
}
vector<li> fact(G+1);
bool pastLim=false;
int emOffset;
li calc(int msk,int em,int treba){
int x=__builtin_popcount(msk);
bitset<M2> aa=msk;
//cout << aa << " " << em << " " << treba << endl;
if(K-x+em+emOffset==K){ // took everything, base case :)
if(!pastLim){
for(int i=0;i<K;i++){
if(msk&(1<<i)){
treba-=K-emOffset-1-mybot[i];
}
}
if(treba<0||treba>G*G)return 0;
//printf("Treba: %i\n",treba);
//printf("Opcija: %i\n",(int)total[em+emOffset][treba]);
return total[em+emOffset][treba]*fact[em]*fact[em+emOffset];
}
else{
assert(msk==0&&em==0);
return treba==0;
}
}
while(sz(bot[msk][em])<=treba)bot[msk][em].pb(-1);
if(bot[msk][em][treba]!=-1)return bot[msk][em][treba];
li val=0;
int vecUzeo=K-x+em;
for(int i=0;i<K;i++){
if(msk&(1<<i)){
int taking=mybot[i];
int ad=abs(taking-vecUzeo);
if(ad<=treba){
val+=calc(msk^(1<<i),em,treba-ad);
}
}
}
if(sz(havetop)){
int ad=K-emOffset-vecUzeo;
if(ad<=treba){
val+=calc(msk,em+1,treba-ad);
}
}
bot[msk][em][treba]=val;
return val;
}
li getbot(int treba){
if(treba<0)return 0;
reset();
return calc((1<<K)-1,0,treba);
}
vector<int> ans;
int LIMIT;
ll tim;
void calcans(li treba){
//printf("%i: %lld\n",sz(ans),clock()-tim);
if(sz(ans)==n){
assert(treba==1);
for(auto p:ans){
printf("%i ",p+1);
}
printf("\n");
return;
}
/*printf("%i!\n",sz(ans));
for(auto p:ans)printf("%i ",p);
printf("\n");
for(auto p:havebot)printf("%i ",p);
printf("\n");
for(auto p:havetop)printf("%i ",p);
printf("\n");*/
if(sz(ans)==LIMIT){
// Convert all the top to bot case
// TODO
for(auto p:havetop)havebot.insert(p);
havetop.clear();
LIMIT=N+1;
pastLim=1;
}
// Take something from bot
vector<int> opt;
for(auto p:havebot)opt.pb(p);
for(auto p:opt){
havebot.erase(p);
ans.pb(p);
int tr=b;
emOffset=0;
for(int i=0;i<sz(ans);i++){
if(ans[i]<LIMIT){
// small
tr-=abs(i-ans[i]);
}
else{
emOffset++;
tr-=LIMIT-i;
}
}
mybot.clear();
for(auto d:havebot){
mybot.pb(d-sz(ans));
}
li my=getbot(tr);
//printf("Pokusavam %i: %i\n",p,(int)my);
if(my>=treba){
calcans(treba);
return;
}
treba-=my;
ans.pop_back();
havebot.insert(p);
}
// Take something from top
opt.clear();
for(auto p:havetop)opt.pb(p);
for(auto p:opt){
havetop.erase(p);
ans.pb(p);
remove(p-LIMIT);
int tr=b;
emOffset=0;
for(int i=0;i<sz(ans);i++){
if(ans[i]<LIMIT){
// small
tr-=abs(i-ans[i]);
}
else{
emOffset++;
tr-=LIMIT-i;
}
}
//printf("Limit = %i\n",LIMIT);
mybot.clear();
for(auto d:havebot){
mybot.pb(d-sz(ans));
}
li my=getbot(tr);
//printf("Pokusavam 2 %i: %i\n",p,(int)my);
if(my>=treba){
calcans(treba);
return;
}
treba-=my;
ans.pop_back();
havetop.insert(p);
undo();
}
assert(0);
}
int main()
{
tim=clock();
fact[0]=1;
for(int i=1;i<=G;i++)fact[i]=i*fact[i-1];
scanf("%i %i",&n,&b);
string s;
cin >> s;
li k=0;
for(auto p:s){
k*=10;
k+=p-'0';
}
//n=b=k=6;
if(n>G){
calctop();
//printf("Done calctop!\n");
for(int i=0;i<n-G;i++){
havebot.insert(i);
}
for(int i=n-G;i<n;i++)havetop.insert(i);
LIMIT=n-G;
}
else{
for(int i=0;i<n;i++)havebot.insert(i);
LIMIT=n;pastLim=1;
}
calcans(k);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20064kb
input:
6 6 6
output:
1 2 6 3 4 5
result:
ok 6 numbers
Test #2:
score: -100
Memory Limit Exceeded
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