제출 #1170764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170764		fesdrer	Shuffle (NOI19_shuffle)	C++17	20 / 100	1 ms	328 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
namespace Solve1{
	int to[5][10],id[10];
	void add(vector<int> i,int z){
		to[z][i[0]]=i[1];
		to[z][i[1]]=i[0];
	}
	vector<int> solve1(){
		vector<vector<int>> rlt1=shuffle({{1,2},{3,4},{5,6}});
		vector<vector<int>> rlt2=shuffle({{1,3},{2,4},{5,6}});
		vector<vector<int>> rlt3=shuffle({{1,5},{3,4},{2,6}});
		vector<vector<int>> rlt4=shuffle({{1,6},{3,2},{5,4}});
		for(auto i:rlt1)	add(i,1);
		for(auto i:rlt2)	add(i,2);
		for(auto i:rlt3)	add(i,3);
		for(auto i:rlt4)	add(i,4);
		vector<int> ret(6,0);
		for(int i=1;i<=6;i++){
			if(to[2][i]==to[1][i])	id[i]=3;
			else if(to[3][i]==to[1][i])	id[i]=2;
			else	id[i]=1;
		}
		for(int i=1;i<=6;i++){
			if(id[i]==1){
				if(id[to[4][i]]==3)	ret[0]=i;
				else	ret[1]=i;
			}
			else if(id[i]==2){
				if(id[to[4][i]]==1)	ret[2]=i;
				else	ret[3]=i;
			}
			else{
				if(id[to[4][i]]==2)	ret[4]=i;
				else	ret[5]=i;
			}
		}
		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++;
		//cout<<cnt3<<endl;
		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);
		/*for(int i:rlt1[0])	cout<<i<<" ";
		cout<<endl;
		for(int i:rlt1[1])	cout<<i<<" ";
		cout<<endl;
		for(int i:rlt2[0])	cout<<i<<" ";
		cout<<endl;
		for(int i:rlt2[1])	cout<<i<<" ";
		cout<<endl;
		for(int i:rlt3[0])	cout<<i<<" ";
		cout<<endl;
		for(int i:rlt3[1])	cout<<i<<" ";
		cout<<endl;*/
		pair<int,int> dif1=find(rlt1,rlt2),dif2=find(rlt1,rlt3);
		//cout<<dif1.first<<" "<<dif1.second<<endl;
		//cout<<dif2.first<<" "<<dif2.second<<endl;
		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;
//cerr<<val<<endl;
		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;
	}
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
	if(K==2)	return Solve1::solve1();
	return Solve2::solve2(N);
}

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