算法竞赛2021 ICPC Southeastern Europe Regional Contest_ABC Legacy

//#include "stdafx.h"

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

 #include <queue>

using namespace std;

   

// Case 1: ACB......        Case 2:  ABAC

int n=5;

char vis[201000];

//char abc[2010000]="ABBACC";

 

char abc[201000]="ABCACBABAB";

//priority_queue<pair<  int, int>> a; 

 

queue<int>R;

int main(){

int ac=0,bc=0,cc=0;

int x;

int Ab,Ac,Bc;

  scanf("%d",&n);  

scanf("%s",abc);  

/*

for( x=0;x<2*n;x++)

{

scanf("%d",&num[x][0]);  

scanf("%d",&num[x][1]); 

}  */

 

for( x=0;x<2*n;x++)  

if(abc[x]=='A')ac++;

else if(abc[x]=='B')bc++;

else cc++;

 

// printf("%d %d, %d\n",ac,bc,cc); 

if(ac+bc>=cc && ((ac+bc-cc )%2==0))

   Ab=(ac+bc-cc )/2;

else {printf("NO\n");return 0;}

  if(ac+cc>=bc && ((ac+cc-bc )%2==0))

  Ac=(ac+cc-bc )/2;

else {printf("NO\n");return 0;}

  if(cc+bc>=ac && ((cc+bc-ac )%2==0))

  Bc=(cc+bc-ac )/2;

else {printf("NO\n");return 0;}

 

int tmp=-1;

for( x=0;x<2*n;x++)

if(Bc && abc[x]=='B')

{

if(tmp<x) tmp=x+1;

while( abc[tmp]!='C' && tmp <2*n)tmp++; 

if(tmp==2*n){printf("NO\n");return 0;}

R.push (x);  vis[x]=1;

R.push (tmp);   vis[tmp]=1;tmp++; 

Bc--;

}// the end of for( x=0;x<2*n;x++)  

//if(Bc){printf("NO\n");return 0;}

 

tmp=2*n;

  for( x=2*n-1;x>=0;x--)

  if(!vis[x])

if(abc[x]=='B'|| abc[x]=='C')

{

if(tmp>x) tmp=x-1;

while(  abc[tmp]!='A'   && tmp >=0)tmp--; 

if(tmp==-1){printf("NO\n");return 0;}

R.push (tmp);  tmp--;// vis[tmp]=1;

  R.push (x);  //vis[x]=1;   

}// the end of for( x=0;x<2*n;x++)  

printf("YES\n");

int first;

while(!R.empty())

{

first= R.front()+1;

R.pop(); 

printf("%d %d\n",first,R.front() +1);

R.pop();   

}

return 0;

}