算法竞赛2021 ICPC Southeastern Europe Regional Contest_Jason ABC
#include "stdafx.h"
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#include <queue>
using namespace std;
int n=3;
//char abc[2010000]="ABBACC";
char abc[11000000]="CBCBCBCB BCCCCC";
int Ac[11000000],Cc[11000000],Bc[11000000];
//priority_queue<pair< int, int>> a;
int main(){
int x,i,j;
//scanf("%d",&n);
//scanf("%s",abc);
Ac[0]=0;
Bc[0]=0;
Cc[0]=0;
for( x=1;x<=3*n;x++)
{
Ac[x]=Ac[x-1];
Bc[x]=Bc[x-1];
Cc[x]=Cc[x-1];
if(abc[x-1]=='A') Ac[x]=Ac[x-1]+1;
if(abc[x-1]=='B') Bc[x]=Bc[x-1]+1;
if(abc[x-1]=='C') Cc[x]=Cc[x-1]+1;
}
//for( x=1;x<=3*n;x++)printf("x= %d %d %d\n",Ac[x],Bc[x],Cc[x]);
if(Ac[3*n]==n && Bc[3*n]==n ){printf("0\n");return 0;}
j=1;
if(Ac[3*n]<n && Bc[3*n]>=n && Cc[3*n]>=n)// possible one operation
{
for(i=0;i<3*n;i++)
{
if(abc[i]=='A')continue;
if(j<i)j=i+1;
while(Bc[j]-Bc[i]<Bc[3*n]-n && j<3*n)j++;
while(Cc[j]-Cc[i]<Cc[3*n]-n && j<3*n)j++;
if(Bc[j]-Bc[i]==Bc[3*n]-n && Cc[j]-Cc[i]==Cc[3*n]-n)
{
printf("1\n%d %d %c\n",i+1,j,'A');
return 0;
}
}
}
j=1;
if(Bc[3*n]<n && Ac[3*n]>=n && Cc[3*n]>=n)// possible one operation
{
for(i=0;i<3*n;i++)
{
if(abc[i]=='B')continue;
if(j<i)j=i+1;
while(Ac[j]-Ac[i]<Ac[3*n]-n && j<3*n)j++;
while(Cc[j]-Cc[i]<Cc[3*n]-n && j<3*n)j++;
if(Ac[j]-Ac[i]==Ac[3*n]-n && Cc[j]-Cc[i]==Cc[3*n]-n)
{
printf("1\n%d %d %c\n",i+1,j,'B');
return 0;
}
}
}
j=1;
if(Cc[3*n]<n && Ac[3*n]>=n && Bc[3*n]>=n)// possible one operation
{
for(i=0;i<3*n;i++)
{
if(abc[i]=='C')continue;
if(j<i)j=i+1;
while(Ac[j]-Ac[i]<Ac[3*n]-n && j<3*n)j++;
while(Bc[j]-Bc[i]<Bc[3*n]-n && j<3*n)j++;
if(Ac[j]-Ac[i]==Ac[3*n]-n && Bc[j]-Bc[i]==Bc[3*n]-n)
{
printf("1\n%d %d %c\n",i+1,j,'C');
return 0;
}
}
}
int k,l,m;
m=3*n;j=n;
while(Ac[j]<n&&Bc[j]<n&&Cc[j]<n) j++;
if(Ac[j]==n){
l=j+n-Cc[j]+1;
printf("2\n%d %d %c\n%d %d %c\n",j+1,l-1,'C',l,m,'B');
return 0;
}
if(Bc[j]==n){
l=j+n-Ac[j]+1;
printf("2\n%d %d %c\n%d %d %c\n",j+1,l-1,'A',l,m,'C');
return 0;
}
if(Cc[j]==n){
l=j+n-Ac[j]+1;
printf("2\n%d %d %c\n%d %d %c\n",j+1,l-1,'A',l,m,'B');
return 0;
}
return 0;
}
