結果
| 問題 |
No.2107 Entangled LIS
|
| コンテスト | |
| ユーザー |
 vjudge1
|
| 提出日時 | 2024-12-07 15:29:07 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 47 ms / 2,000 ms |
| コード長 | 4,229 bytes |
| コンパイル時間 | 2,865 ms |
| コンパイル使用メモリ | 37,092 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2024-12-07 15:29:17 |
| 合計ジャッジ時間 | 3,006 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
コンパイルメッセージ
main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
28 | main()
| ^~~~
ソースコード
#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()
{
// freopen("array.in","r",stdin);
// freopen("array.out","w",stdout);
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)
{
if(b==1)
{
for(i=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();
continue;
}
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();
}
}
}