QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639265#8529. Balance of Permutationucup-team134ML 0ms20064kbC++175.8kb2024-10-13 18:37:312024-10-13 18:37:41

Judging History

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

  • [2024-10-13 18:37:41]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:20064kb
  • [2024-10-13 18:37:31]
  • 提交

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

详细

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 

result: