QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#347116#8046. Rock-Paper-Scissors Pyramidcrsfaa#TL 0ms7892kbC++142.2kb2024-03-09 11:11:462024-03-09 11:11:47

Judging History

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

  • [2024-03-09 11:11:47]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7892kb
  • [2024-03-09 11:11:46]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
/*
S->P
P->R
R->S

0 1 2
*/
const int mxn=1e6+5;
char s[mxn];
struct node
{
	int k,b;
	char c;
}c[mxn];
int mp[300][300];
int pre[mxn],nxt[mxn];
bool del[mxn];
int main()
{
	mp['S']['P']=mp['P']['R']=mp['R']['S']=1;
	int T=read();
	while(T--)
	{
		scanf("%s",s+1);
		int n=strlen(s+1),i,j,top=0,cc;
		c[++top]={0,0,0};
		c[++top]={0,1,s[1]};
		for(i=2;i<=n;i++)
			if(s[i]==c[top].c)
				c[top].b++;
			else
				c[++top]={0,1,s[i]};
		c[++top]={0,0,0};
		for(i=1;i<=top;i++)
			pre[i]=i-1,nxt[i]=i+1;
		memset(del,0,top+1);
		set<pair<int,int>> st;
		for(i=2;i<top;i++)
		{
			c[i].k=-1;
			c[i].k+=mp[c[i].c][c[i-1].c];
			c[i].k+=mp[c[i].c][c[i+1].c];
			if(c[i].k<0)
				st.insert({c[i].b,i});
		}
		del[1]=del[top]=1;
//		for(i=2;i<top;i++)
//			cout<<c[i].k<<' '<<c[i].b<<' '<<c[i].c<<endl;
		cc=top-2;
		//kx<=-b
		while(cc>1)
		{
			vector<int> pos;
			int mn=st.begin()->first;
			for(;st.begin()->first==mn&&st.size();st.erase(st.begin()))
			{
				int w=st.begin()->second;
				nxt[pre[w]]=nxt[w],pre[nxt[w]]=pre[w];
				del[w]=1;
				pos.push_back(pre[w]),pos.push_back(nxt[w]);
//				cout<<"del "<<w<<endl;
				cc--;
			}
			sort(pos.begin(),pos.end());
			pos.resize(unique(pos.begin(),pos.end())-pos.begin());
			for(auto i:pos)
				if(!del[i])
				{
					if(c[i].k<0)
						st.erase({c[i].b,i});
					//(i-mn)*k0+b
					int k0=-1;
					k0+=mp[c[i].c][c[pre[i]].c];
					k0+=mp[c[i].c][c[nxt[i]].c];
					c[i]={k0,-mn*k0+c[i].b,c[i].c};
					if(c[i].k<0)
						st.insert({c[i].b,i});
				}
			for(auto i:pos)
				if(!del[i]&&c[nxt[i]].c==c[i].c)
				{
//					cout<<"merge "<<i<<' '<<nxt[i]<<endl;
					if(c[i].k<0)
						st.erase({c[i].b,i});
					if(c[nxt[i]].k<0)
						st.erase({c[nxt[i]].b,nxt[i]});
					c[nxt[i]].k+=c[i].k+1;
					if(c[nxt[i]].k<0)
						st.insert({c[nxt[i]].b,nxt[i]});
				}
		}
		putchar(c[st.begin()->second].c),puts("");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7892kb

input:

2
SPR
SPSRRP

output:

S
P

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1
RPPSRPPRSRSRRRPPSPRPRSRRSRRPPPRSPSSRRRSPPPRRRPRRRSSRPSSRPRRPSRRRPRSRPSRPSRRSPPRPRRRSPRSSSRPRRRPPSRRRRPPSRSRRRPRPRPRPPRRSRRPSRPPSRRRSRRSRRSPSRPRPSPSSRRSPSPSRPRRRPPRSRSPSPPRRPRSRPPSSSRPSPRRPSSSPRRSRRSRRSRSPSSSSRSSPPRRRRPRRRSPSRSPRSSPRSPSPRPRRRPPRPPRPPPSRRRRSSPRRSRRRPRRRSSRRPSRPPRSPPSPPPSPSPSPPSSPRRR...

output:


result: