题意

分析

考场做法同题解一样。

std代码。

#include<bits/stdc++.h>

using namespace std;

template <typename T> void chmin(T&x,const T &y)

{

	if(x>y)x=y;

}

template <typename T> void chmax(T &x,const T &y)

{

	if(x<y)x=y;

}

typedef long long s64;

typedef unsigned long long u64;

typedef unsigned int u32;

typedef pair<int,int> pii;

#define rep(i,l,r) for(int i=l;i<=r;++i)

#define per(i,r,l) for(int i=r;i>=l;--i)

#define rep0(i,l,r) for(int i=l;i<r;++i)

#define gc (c=getchar())

int read()

{

	char c;

	while(gc<'-');

	if(c=='-')

	{

		int x=gc-'0';

		while(gc>='0')x=x*10+c-'0';

		return -x;

	}

	int x=c-'0';

	while(gc>='0')x=x*10+c-'0';

	return x;

}

#undef gc

int n,need_a[3];

const char s[]="RPS";

string write(int n,int x)

{

	if(!n)

	{

		string ans;

		ans.push_back(s[x]);

		return ans;

	}

	string a=write(n-1,x),b=write(n-1,(x+1)%3);

	return a<b?a+b:b+a;

}

bool check(int x)

{

	int a[3]={},a0[3];

	a[x]=1;

	rep(tmp,1,n)

	{

		rep(i,0,2)a0[i]=a[i];

		rep(i,0,2)a[(i+1)%3]+=a0[i];

	}

	//cerr<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;

	rep(i,0,2)

	if(a[i]!=need_a[i])return 0;

	cout<<write(n,x)<<endl;

	return 1;

}

int main()

{

	freopen("rps.in","r",stdin);freopen("rps.out","w",stdout);

		rep(i,0,2)need_a[i]=read();

		n=0;

		while((1<<n)!=need_a[0]+need_a[1]+need_a[2])++n;

		int i=0;

		for(;i<=2;++i)

		if(check(i))break;

		if(i>2)puts("IMPOSSIBLE");

}

我的代码。排序的时候我用的递推处理，跑得比std快。

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=1<<20|7;

int a[2][MAXN],len[2];

int cur;

int main()

{

  freopen("rps.in","r",stdin);

  freopen("rps.out","w",stdout);

	int R,P,S;

	read(R);read(P);read(S);

	int n;

	for(int i=1;i<=20;++i)

		if(R+P+S==(1<<i))

			n=i;

//	cerr<<"n="<<n<<endl;

	for(int i=1;i<=3;++i)

	{

		cur=0;

		len[cur]=0;

		a[cur][++len[cur]]=i;

		for(int j=1;j<=n;++j)

		{

			cur^=1;

			len[cur]=0;

			for(int k=1;k<=len[cur^1];++k)

			{

				if(a[cur^1][k]==1)

				{

					a[cur][++len[cur]]=1;

					a[cur][++len[cur]]=2;

				}

				else if(a[cur^1][k]==2)

				{

					a[cur][++len[cur]]=2;

					a[cur][++len[cur]]=3;

				}

				else

				{

					a[cur][++len[cur]]=1;

					a[cur][++len[cur]]=3;

				}

			}

		}

		int r=0,p=0,s=0;

		for(int j=1;j<=len[cur];++j)

		{

			if(a[cur][j]==1)

				++p;

			else if(a[cur][j]==2)

				++r;

			else

				++s;

		}

		if(R==r&&P==p&&S==s)

		{

			for(int l=1;l<=n;++l) // the log of the sum of swap len

			{

				int d=(1<<l); // the sum of swap len

				for(int j=1;j<len[cur];j+=d)

				{

					int x=j,y=j+(d>>1);

					while(a[cur][x]==a[cur][y]&&x<j+(d<<1))

						++x,++y;

					if(x<j+(d<<1))

					{

//						cerr<<"x="<<x<<" y="<<y<<endl;

//						cerr<<"cmp"<<a[cur][x]<<" "<<a[cur][y]<<endl;

						if(a[cur][x]<a[cur][y])

							continue;

//						cerr<<"swap fr "<<j<<" to "<<(j+(d>>1))<<endl;

						for(int k=j;k<j+(d>>1);++k)

							swap(a[cur][k],a[cur][k+(d>>1)]);

					}

				}

			}

			for(int j=1;j<=len[cur];++j)

			{

				if(a[cur][j]==1)

					putchar('P');

				else if(a[cur][j]==2)

					putchar('R');

				else

					putchar('S');

			}

			puts("");

			return 0;

		}

	}

	puts("IMPOSSIBLE");

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}