算法競賽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;
}