QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#347116 | #8046. Rock-Paper-Scissors Pyramid | crsfaa# | TL | 0ms | 7892kb | C++14 | 2.2kb | 2024-03-09 11:11:46 | 2024-03-09 11:11:47 |
Judging History
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...