Submission #1170853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170853		fesdrer	Shuffle (NOI19_shuffle)	C++17	100 / 100	70 ms	584 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
namespace Solve1{
	int to[5][1005];
	void get(vector<vector<int>> rlt,int id){
		for(vector<int> i:rlt)	to[id][i[0]]=i[1],to[id][i[1]]=i[0];
	}
	vector<int> solve1(int n){
		vector<vector<int>> tmp(0);
		for(int i=1;i<=n;i+=2)	tmp.push_back({i,i+1});
		vector<vector<int>> rlt=shuffle(tmp);
		get(rlt,1);
		tmp.clear();
		for(int i=2;i<n;i+=2)	tmp.push_back({i,i+1});
		tmp.push_back({n,1});
		rlt=shuffle(tmp);
		get(rlt,2);
		tmp.clear(),tmp.push_back({1,3}),tmp.push_back({2,4});
		for(int i=5;i<=n;i+=2)	tmp.push_back({i,i+1});
		rlt=shuffle(tmp);
		get(rlt,3);
		tmp.clear(),tmp.push_back({2,4}),tmp.push_back({3,5});
		for(int i=6;i<n;i+=2)	tmp.push_back({i,i+1});
		tmp.push_back({n,1});
		rlt=shuffle(tmp);
		get(rlt,4);
		vector<int> ret(0);
		int st=0;
		for(int i=1;i<=n;i++)	if(to[3][i]!=to[1][i]&&to[4][i]==to[2][i]){
			st=i;ret.push_back(i);break;
		}
		st=to[1][st],ret.push_back(st);
		for(int i=2;i<=n/2;i++){
			st=to[2][st],ret.push_back(st);
			st=to[1][st],ret.push_back(st);
		}
		return ret;
	}
}
namespace Solve2{
	int tag[1005];
	int lazy1[1005],lazy2[1005],rnk[10000];
	pair<int,int> find(vector<vector<int>> x,vector<vector<int>> y){
		for(int i:x[0])	tag[i]++;
		for(int i:y[0])	tag[i]+=2;
		int cnt3=0;
		for(int i=1;i<=1000;i++)	if(tag[i]==3)	cnt3++;
		if(cnt3==int(x[0].size())-1){
			pair<int,int> ret={0,0};
			for(int i=1;i<=1000;i++)	if(tag[i]==2)	ret.first=i;
			for(int i=1;i<=1000;i++)	tag[i]=0;
			for(int i:x[1])	tag[i]++;
			for(int i:y[1])	tag[i]+=2;
			for(int i=1;i<=1000;i++)	if(tag[i]==2)	ret.second=i;
			for(int i=1;i<=1000;i++)	tag[i]=0;
			return ret;
		}
		else{
			for(int i=1;i<=1000;i++)	tag[i]=0;
			pair<int,int> ret={0,0};
			for(int i:x[0])	tag[i]++;
			for(int i:y[1])	tag[i]+=2;
			for(int i=1;i<=1000;i++)	if(tag[i]==2)	ret.first=i;
			for(int i=1;i<=1000;i++)	tag[i]=0;
			for(int i:x[1])	tag[i]++;
			for(int i:y[0])	tag[i]+=2;
			for(int i=1;i<=1000;i++)	if(tag[i]==2)	ret.second=i;
			for(int i=1;i<=1000;i++)	tag[i]=0;
			return ret;
		}
	}
	void getlazy(vector<vector<int>> ori,vector<vector<int>> tun,int val,int bit){
		bool flag=0;
		for(int i:ori[0])	if(i==1)	flag=1;
		if(flag)	for(int i:ori[0])	lazy1[i]+=bit;
		else	for(int i:ori[1])	lazy1[i]+=bit;
		flag=0;
		for(int i:tun[0])	if(i==val)	flag=1;
		if(flag)	for(int i:tun[0])	lazy2[i]+=bit;
		else	for(int i:tun[1])	lazy2[i]+=bit;
	}
	vector<int> solve2(int n){
		int len=n/2;
		vector<vector<int>> tmp(2,vector<int>(0));
		for(int i=1;i<=len;i++)	tmp[0].push_back(i);
		for(int i=len+1;i<=n;i++)	tmp[1].push_back(i);
		vector<vector<int>> rlt1=shuffle(tmp);
		tmp[0].clear(),tmp[1].clear();
		tmp[0].push_back(len+1),tmp[1].push_back(1);
		for(int i=2;i<=len;i++)	tmp[0].push_back(i);
		for(int i=len+2;i<=n;i++)	tmp[1].push_back(i);
		vector<vector<int>> rlt2=shuffle(tmp);
		tmp[0].clear(),tmp[1].clear();
		tmp[0].push_back(n),tmp[1].push_back(1);
		for(int i=2;i<=len;i++)	tmp[0].push_back(i);
		for(int i=len+1;i<n;i++)	tmp[1].push_back(i);
		vector<vector<int>> rlt3=shuffle(tmp);
		pair<int,int> dif1=find(rlt1,rlt2),dif2=find(rlt1,rlt3);
		int val=0;
		if(dif1.first==dif2.first)	val=dif1.first;
		else if(dif1.first==dif2.second)	val=dif1.first;
		else if(dif1.second==dif2.first)	val=dif1.second;
		else if(dif1.second==dif2.second)	val=dif1.second;
		tmp[0].clear(),tmp[1].clear();
		for(int i=1;i<=len;i++)	tmp[0].push_back(i);
		for(int i=len+1;i<=n;i++)	tmp[1].push_back(i);
		getlazy(tmp,rlt1,val,1);
		for(int bit=1;bit<=len;bit<<=1){
			tmp[0].clear(),tmp[1].clear();
			for(int i=1;i<=len;i++){
				if(i&bit)	tmp[0].push_back(i),tmp[1].push_back(i+len);
				else	tmp[1].push_back(i),tmp[0].push_back(i+len);
			}
			vector<vector<int>> rltnow=shuffle(tmp);
			getlazy(tmp,rltnow,val,bit<<1);
		}
		for(int i=1;i<=n;i++)	rnk[lazy2[i]]=i;
		vector<int> ret(0);
		for(int i=1;i<=n;i++)	ret.push_back(rnk[lazy1[i]]);
		return ret;
	}
}
namespace Solve3{
	struct Node{
		int st,orist;
		vector<int> member;
	}s[1005];
	int f2t1[1005],f1t2more[1005],tag[1005];
	void init(vector<vector<int>> rlt1,vector<vector<int>> rlt2,int n,int B,int K){
		for(int i=0;i<B;i++){
			memset(tag,0,sizeof tag);
			for(int p:rlt1[i])	tag[p]++;
			for(int j=0;j<B;j++){
				for(int p:rlt2[j])	tag[p]+=2;
				int cnt=0;
				for(int p=1;p<=n;p++)	if(tag[p]==3)	cnt++;
				if(cnt==K-1){
					f2t1[j]=i;
					for(int p=1;p<=n;p++){
						if(tag[p]==1)	s[i].st=p;
						else if(tag[p]==2)	f1t2more[i]=p;
						else if(tag[p]==3)	s[i].member.push_back(p);
					}
					break;
				}
				for(int p:rlt2[j])	tag[p]-=2;
			}
		}
	}
	void getorist(vector<vector<int>> rlt2,vector<vector<int>> rlt3,int n,int B,int K){
		int id=0;
		for(int i=0;i<B;i++){
			bool flagg=1;
			for(int j=0;j<B&&flagg;j++){
				memset(tag,0,sizeof tag);
				for(int p:rlt2[i])	tag[p]++;
				for(int p:rlt3[j])	tag[p]--;
				bool flag=1;
				for(int p=1;p<=n;p++)	if(tag[p])	flag=0;
				if(flag)	flagg=0;
			}
			if(!flagg){
				id=i;
				break;
			}
		}
		id=f2t1[id];
		for(int i=0;i<B;i++){
			s[id].orist=i,id=f1t2more[id];
			for(int j=0;j<B;j++)	if(s[j].st==id){
				id=j;break;
			}
		}
	}
	int belongid[1005],toptag[1005],val[1005];
	vector<int> solve(int n,int B,int K){
		vector<vector<int>> tmp(B,vector<int>(0));
		for(int i=0;i<B;i++)	for(int j=K;j>=1;j--)	tmp[i].push_back(j+i*K);
		vector<vector<int>> rlt1=shuffle(tmp);
		tmp[0].back()+=K,tmp[1].back()-=K;
		vector<vector<int>> rlt3=shuffle(tmp);
		for(int i=0;i<B;i++){
			tmp[i].clear(),tmp[i].push_back((i+1)%B*K+1);
			for(int j=2;j<=K;j++)	tmp[i].push_back(j+i*K);
		}
		vector<vector<int>> rlt2=shuffle(tmp);
		init(rlt1,rlt2,n,B,K);
		getorist(rlt2,rlt3,n,B,K);
		sort(s,s+B,[&](const Node &x,const Node &y){return x.orist<y.orist;});
		//for(int i=0;i<B;i++){
		//	cout<<s[i].st<<" "<<s[i].orist<<endl;
		//	for(int j:s[i].member)	cout<<j<<" ";
		//	cout<<endl;
		//}
		for(int i=0;i<B;i++){
			toptag[s[i].st]=1,belongid[s[i].st]=i;
			for(int j:s[i].member)	belongid[j]=i;
		}
		for(int bit=1;bit<=K;bit*=B){
			for(int i=0;i<B;i++){
				tmp[i].clear();
				tmp[i].push_back(i*K+1);
			}
			for(int i=0;i<B;i++){
				for(int j=2;j<=K;j++){
					int p=(i+(j/bit)%B)%B;
					tmp[p].push_back(j+i*K);
				}
			}
			vector<vector<int>> rlt=shuffle(tmp);
			for(int i=0;i<B;i++){
				int nowid=0;
				for(int j:rlt[i])	if(toptag[j]){
					nowid=belongid[j];break;
				}
				for(int j:rlt[i])	if(!toptag[j])
					val[j]+=bit*((nowid+B-belongid[j])%B);
			}
		}
		vector<int> ret(0);
		for(int i=0;i<B;i++){
			sort(s[i].member.begin(),s[i].member.end(),[&](const int &x,const int &y){
				return val[x]<val[y];
			});
			ret.push_back(s[i].st);
			for(int j:s[i].member)	ret.push_back(j);
		}
		//for(int i:ret)	cout<<i<<" "<<val[i]<<endl;
		//cout<<endl;
		return ret;
	}
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
	if(K==2)	return Solve1::solve1(N);
	if(B==2)	return Solve2::solve2(N);
	return Solve3::solve(N,B,K);
}

• Subtask 1: 2 / 2
• Subtask 2: 3 / 3
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 15 / 15
• Subtask 6: 52 / 52