QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71320 | #4273. Good Game | zhouhuanyi | 0 | 0ms | 0kb | C++14 | 3.6kb | 2023-01-09 17:27:05 | 2023-01-09 17:27:06 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<set>
#define N 2000000
#define inf 1e9
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data;
bool operator < (const reads &t)const
{
return (data!=t.data)?data>t.data:num<t.num;
}
};
reads st[N+1];
set<reads>s;
int n,length,leng,tong[N+1],pv[N+1],nt[N+1],rt[N+1],L[N+1],R[N+1],sc[N+1];
char c[N+1];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int d)
{
for (;x<=length;x+=lowbit(x)) sc[x]+=d;
return;
}
int query(int x)
{
int res=0;
for (;x>=1;x-=lowbit(x)) res+=sc[x];
return res;
}
void del(int x)
{
int s1=pv[x],s2=nt[x];
nt[s1]=s2,pv[s2]=s1;
if (tong[x]==1)
{
s.erase((reads){rt[x],R[rt[x]]-L[rt[x]]+1});
if (L[rt[x]]==x) L[rt[x]]++;
else R[rt[x]]--;
if (L[rt[x]]<=R[rt[x]]) s.insert((reads){rt[x],R[rt[x]]-L[rt[x]]+1});
}
nt[x]=pv[x]=-1;
return;
}
void solve(int x)
{
for (int i=1;i<=(tong[x]>>1);++i) st[++leng]=(reads){query(x-1)+1,2};
if (tong[x]&1) st[leng].data++;
if (pv[x]&&nt[x]!=length+1) add(pv[x],-tong[pv[x]]),add(nt[x],-tong[nt[x]]),add(x,tong[pv[x]]+tong[nt[x]]-tong[x]),tong[x]=tong[pv[x]]+tong[nt[x]],del(pv[x]),del(nt[x]);
else add(x,-tong[x]),del(x);
return;
}
int main()
{
freopen("strings.in","r",stdin);
freopen("strings.out","w",stdout);
int lst=0,cnt0=0,cnt1=0,cnt,rst=0,mid=0,top;
bool op=1;
n=read();
for (int i=1;i<=n;++i) cin>>c[i];
for (int i=1;i<=n;++i)
if (i==n||c[i]!=c[i+1])
tong[++length]=i-lst,lst=i;
for (int i=1;i<=length;++i) add(i,tong[i]);
for (int i=1;i<=length-1;++i) cnt0+=(tong[i]==1&&tong[i+1]>=2),cnt1+=(tong[i]>=2&&tong[i+1]==1);
for (int i=0;i<=length;++i) nt[i]=i+1,pv[i+1]=i;
for (int i=1;i<=length;++i)
{
if ((i==1||tong[i-1]>=2)&&tong[i]==1) lst=i;
rt[i]=lst;
if ((i==length||tong[i+1]>=2)&&tong[i]==1) L[lst]=lst,R[lst]=i,s.insert((reads){lst,R[lst]-L[lst]+1}),op&=(((i-lst+1)<<1)<=(length-(lst!=1)-(i!=length)));
}
if (tong[1]==1&&cnt0==1&&cnt1==1)
{
cnt0=cnt1=0;
for (int i=1;i<=length;++i)
{
if (tong[i]==1) cnt0++;
else break;
}
for (int i=length;i>=1;--i)
{
if (tong[i]==1) cnt1++;
else break;
}
cnt=length-cnt0-cnt1;
if (cnt>=((n+1)>>1)||((length&1)&&op))
{
if (cnt>=((n+1)>>1))
{
for (int i=1;i<=(cnt0<<1);++i) solve(cnt0+1);
for (int i=1;i<=(cnt1<<1);++i) solve(length-cnt1);
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
solve(i);
}
else
{
if (cnt0<cnt1)
{
for (int i=1;i<=cnt1-cnt0;++i) solve(length-cnt1);
}
else
{
for (int i=1;i<=cnt0-cnt1;++i) solve(cnt0+1);
}
cnt=0;
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
cnt++;
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
{
rst++;
if (rst==((cnt+1)>>1)) mid=i;
}
for (int i=1;i<=((cnt+1)>>1);++i) solve(mid);
}
printf("%d\n",leng);
for (int i=1;i<=leng;++i) printf("%d %d\n",st[i].num,st[i].data);
}
else puts("-1");
return 0;
}
if (op)
{
while (!s.empty())
{
top=(*s.begin()).num;
if (pv[L[top]]!=-1&&pv[pv[L[top]]]&&tong[pv[L[top]]]>=2) solve(pv[L[top]]);
else solve(nt[R[top]]);
}
for (int i=1;i<=length;++i)
if (nt[i]!=-1)
solve(i);
printf("%d\n",leng);
for (int i=1;i<=leng;++i) printf("%d %d\n",st[i].num,st[i].data);
}
else puts("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
9 ABAABBBAA
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #51:
score: 0
Dangerous Syscalls
input:
299 ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...
output:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #102:
score: 0
Dangerous Syscalls
input:
5998 BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
result:
Subtask #4:
score: 0
Dangerous Syscalls
Test #153:
score: 0
Dangerous Syscalls
input:
999997 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...