結果

問題 No.2107 Entangled LIS
ユーザー vjudge1vjudge1
提出日時 2024-12-07 15:15:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,917 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 37,168 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-12-07 15:15:40
合計ジャッジ時間 2,865 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 22 ms
5,248 KB
testcase_04 AC 27 ms
5,248 KB
testcase_05 AC 40 ms
5,248 KB
testcase_06 AC 40 ms
5,248 KB
testcase_07 AC 43 ms
5,248 KB
testcase_08 AC 49 ms
6,528 KB
testcase_09 AC 45 ms
6,400 KB
testcase_10 AC 26 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main()
      | ^~~~

ソースコード

diff # 

#include<cstdio>
using namespace std;
int T,I,i,z,n,a,b,flag,la[210000],rb[210000],ansa[210000],ansb[210000],topl,topr;
char s[210000];
void print()
{
	int i;
	printf("Yes\n");
	if(flag==0)
	{
		for(i=1;i<=n;i++)
		printf("%d ",ansa[i]);
		printf("\n");
		for(i=1;i<=n;i++)
		printf("%d ",ansb[i]);
		printf("\n");
	}
	else
	{
		for(i=1;i<=n;i++)
		printf("%d ",ansb[i]);
		printf("\n");
		for(i=1;i<=n;i++)
		printf("%d ",ansa[i]);
		printf("\n");
	}
}
main()
{
	scanf("%d",&T);
	for(I=1;I<=T;I++)
	{
		scanf("%d%d%d\n%s",&n,&a,&b,s+1);
		if(a>b)
		{
			flag=1;
			i=a;
			a=b;
			b=i;
			for(i=1;i<=n;i++)
			if(s[i]=='a')
			s[i]='b';
			else
			s[i]='a';
		}
		else
		flag=0;
		for(i=1;i<=n;i++)
		{
			ansa[i]=0;
			ansb[i]=0;
		}
		topl=1;
		topr=n*2;
		if(a==1)
		{
			for(i=1;i<=n;i++)
			if(s[i]=='a')
			la[i]=la[i-1]+1;
			else
			la[i]=la[i-1];
			rb[n+1]=0;
			for(i=n;i>=1;i--)
			if(s[i]=='b')
			rb[i]=rb[i+1]+1;
			else
			rb[i]=rb[i+1];
			if(la[n]>=b&&s[n]=='a')
			{
				for(i=n;i>=1;i--)
				if(s[i]=='a')
				{
					ansb[i]=b-topl+1;
					topl++;
					if(topl>b)
					break;
				}
				for(i=1;i<=n;i++)
				if(ansb[i]!=0)
				{
					ansa[i]=topr;
					topr--;
				}
				else
				{
					if(s[i]=='a')
					{
						ansa[i]=topr;
						ansb[i]=topr-1;
					}
					else
					{
						ansa[i]=topr-1;
						ansb[i]=topr;
					}
					topr=topr-2;
				}
				print();
				continue;
			}
			if(rb[1]>=b&&s[1]=='b')
			{
				for(i=1;i<=n;i++)
				if(s[i]=='b')
				{
					ansb[i]=n*4-b+1-topr;
					topr--;
					if(topr<=n*2-b)
					break;
				}
				for(i=1;i<=n;i++)
				if(ansb[i]!=0)
				{
					ansa[i]=topr;
					topr--;
				}
				else
				{
					if(s[i]=='a')
					{
						ansa[i]=topr;
						ansb[i]=topr-1;
					}
					else
					{
						ansa[i]=topr-1;
						ansb[i]=topr;
					}
					topr=topr-2;
				}
				print();
				continue;
			}
			for(i=1;i<=n;i++)
			if(la[i-1]+rb[i]>=b&&s[i-1]=='a'&&s[i]=='b')
			break;
			if(i>n)
			{
				printf("No\n");
				continue;
			}
			z=i;
			for(i=0;i<=n;i++)
			{
				if(z-i>0&&s[z-i]=='a')
				{
					topl++;
					ansb[z-i]=-1;
					if(topl+n*2-topr>b)
					break;
				}
				if(z+i<=n&&s[z+i]=='b')
				{
					topr--;
					ansb[z+i]=-1;
					if(topl+n*2-topr>b)
					break;
				}
			}
			topl=1;
			topr=n*2;
			for(i=1;i<=n;i++)
			if(ansb[i]==-1&&s[i]=='a')
			{
				ansb[i]=topl;
				topl++;
			}
			for(i=n;i>=1;i--)
			if(ansb[i]==-1)
			{
				ansb[i]=topr;
				topr--;
			}
			for(i=1;i<=n;i++)
			if(ansb[i]!=0)
			{
				ansa[i]=topr;
				topr--;
			}
			else
			{
				if(s[i]=='a')
				{
					ansa[i]=topr;
					ansb[i]=topr-1;
				}
				else
				{
					ansa[i]=topr-1;
					ansb[i]=topr;
				}
				topr=topr-2;
			}
			print();
		}
		else
		{
			topl=2*(n-b)+1;
			for(i=1;i<=b;i++)
			if(s[i]=='b')
			break;
			if(i>b-a)
			{
				for(i=b-a;i>=1;i--)
				if(s[i]=='b')
				{
					ansa[i]=topl;
					topl++;
				}
				for(i=1;i<=b-a;i++)
				if(s[i]=='a')
				{
					ansa[i]=topr;
					topr--;
				}
				for(i=1;i<=b-a;i++)
				{
					ansb[i]=topl;
					topl++;
				}
				for(i=b;i>=b-a+1;i--)
				{
					if(s[i]=='a')
					{
						ansa[i]=topr;
						ansb[i]=topr-1;
					}
					else
					{
						ansa[i]=topr-1;
						ansb[i]=topr;
					}
					topr=topr-2;
				}
			}
			else
			{
				for(i=b-a+1;i>=1;i--)
				if(s[i]=='b')
				{
					ansa[i]=topl;
					topl++;
				}
				for(i=1;i<=b-a+1;i++)
				if(s[i]=='a')
				{
					ansa[i]=topr;
					topr--;
				}
				for(i=1;i<=b-a+1;i++)
				{
					ansb[i]=topl;
					topl++;
				}
				for(i=b;i>=b-a+2;i--)
				{
					if(s[i]=='a')
					{
						ansa[i]=topr;
						ansb[i]=topr-1;
					}
					else
					{
						ansa[i]=topr-1;
						ansb[i]=topr;
					}
					topr=topr-2;
				}
			}
			topr=2*(n-b);
			for(i=b+1;i<=n;i++)
			{
				if(s[i]=='a')
				{
					ansa[i]=topr;
					ansb[i]=topr-1;
				}
				else
				{
					ansa[i]=topr-1;
					ansb[i]=topr;
				}
				topr=topr-2;
			}
			print();
		}
	}
}
0