QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71320#4273. Good Gamezhouhuanyi0 0ms0kbC++143.6kb2023-01-09 17:27:052023-01-09 17:27:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-09 17:27:06]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-01-09 17:27:05]
  • 提交

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...

output:


result: