結果

問題 No.2107 Entangled LIS
ユーザー vjudge1vjudge1
提出日時 2024-12-07 15:46:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,029 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 90,968 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-12-07 15:46:27
合計ジャッジ時間 3,201 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 44 ms
8,192 KB
testcase_09 AC 47 ms
8,064 KB
testcase_10 AC 25 ms
6,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<queue>
#include<ctime>
#include<cmath>
#include<set>
#include<map>
#define infile(filename) freopen(filename".in","r",stdin)
#define outfile(filename) freopen(filename".out","w",stdout)
#define usefile(filename) infile(filename),outfile(filename)
using namespace std; typedef long long ll; typedef unsigned long long ull; typedef __int128 I;
namespace IO {
	const int BUF=1<<20; static char ch[BUF]={},out[BUF]={},*l=ch,*r=ch,*o=out;
#define FASTIO
#ifdef FASTIO
	inline char gc() { return (l==r&&(r=(l=ch)+fread(ch,1,BUF,stdin),l==r))?EOF:*l++; }
#else
	inline char gc() { return getchar(); }
#endif
	inline void flush() { fwrite(out,1,o-out,stdout),o=out; }
	inline void putc(char ch) { if(o==out+BUF) flush(); *o++=ch; }
	struct flusher{~flusher(){flush();}}_;
}; using IO::gc; using IO::putc;
template <typename T> void read(T &a) { static char fushu,ch; a=fushu=0; do ch=gc(); while(ch!='-'&&(ch<48||ch>57)); if(ch=='-') ch=gc(),fushu=1; do a=(a<<1)+(a<<3)+(ch^48),ch=gc(); while(ch>47&&ch<58); if(fushu) a=-a; }
template <typename T,typename ...Args> void read(T &a,Args &...args) { read(a),read(args...); }
template <typename T> void write(T a) { static char que[114]={},*p=que; if(!a) putc(48); if(a<0) putc('-'),a=-a; while(a) *p++=(a%10)^48,a/=10; while(p!=que) putc(*--p); putc(32); }
template <typename T,typename ...Args> void write(T a,Args ...args) { write(a),write(args...); }
const int N=400099;
int T,n,A,B,a[N]={},b[N]={},c[N]={};
namespace taskBF {
	bool ind[N]={},flag;
	int calc(int a[]) {
		static int f[N]={}; int i,j,maxn=0;
		for(i=1;i<=n;++i) {
			f[i]=0;
			for(j=1;j<i;++j)
				if(a[j]<a[i])
					f[i]=max(f[i],f[j]);
			++f[i],maxn=max(maxn,f[i]);
		} return maxn;
	}
	void dg(int x) {
		if(x>n) {
			if(calc(a)==A&&calc(b)==B) {
				flag=true; int i;
				printf("Yes\n");
				for(i=1;i<=n;++i) printf("%d ",a[i]); printf("\n");
				for(i=1;i<=n;++i) printf("%d ",b[i]); printf("\n");
			} return ;
		}
		for(int i=1;i<=2*n&&!flag;++i) if(!ind[i])
			for(int j=i+1;j<=2*n&&!flag;++j) if(!ind[j]) {
				ind[i]=ind[j]=true;
				if(c[x]) b[x]=j,a[x]=i;
				else b[x]=i,a[x]=j;
				dg(x+1);
				ind[i]=ind[j]=false;
			}
		return ;
	}
	void solve() {
		flag=false,dg(1);
		if(!flag) printf("No\n");
	}
}
namespace taskA1 {
	int cnta[N]={},cntb[N]={},plan[N]={};
	void solve(int tag) {
		int i,j;
		if(B==1) {
			for(i=1;i<n;++i) {
				if(!c[i]&&c[i+1]) {
					printf("No\n");
					return ;
				}
			}
		}
		for(i=1,cnta[0]=0;i<=n;++i)
			cnta[i]=cnta[i-1]+(!c[i]);
		for(i=n,cntb[n+1]=0;i;--i)
			cntb[i]=cntb[i+1]+c[i];
		for(i=1;i<=n;++i) a[i]=2*n+1-cntb[1]-i;
		for(i=1,j=A;i<j;++i,--j) swap(a[i],a[j]);
		for(i=1,j=2*n;i<=n;++i) if(c[i]) b[i]=j--;
		for(i=1,j=a[n]-1;i<=n;++i) if(!c[i]) b[i]=j--;
		for(i=1;i<=n;++i)
			if((cnta[i]>0)+(cntb[i]>0)<=B&&B<=cnta[i]+cntb[i]) {
				int pa=(cnta[i]>0),pb=(cntb[i]>0);
				if(pa+pb<B) pa+=min(B-pa-pb,max(0,cnta[i]-1));
				if(pa+pb<B) pb+=min(B-pa-pb,max(0,cntb[i]-1));
				for(plan[0]=0,j=i;plan[0]<pa&&j;--j)
					if(!c[j]) plan[++plan[0]]=j;
				for(int l=1,r=plan[0];l<r;++l,--r)
					swap(b[plan[l]],b[plan[r]]);
				for(plan[0]=0,j=i;plan[0]<pb&&j<=n;++j)
					if(c[j]) plan[++plan[0]]=j;
				for(int l=1,r=plan[0];l<r;++l,--r)
					swap(b[plan[l]],b[plan[r]]);
				printf("Yes\n");
				if(!tag) {
					for(j=1;j<=n;++j) printf("%d ",a[j]); printf("\n");
					for(j=1;j<=n;++j) printf("%d ",b[j]); printf("\n");
				} else {
					for(j=1;j<=n;++j) printf("%d ",b[j]); printf("\n");
					for(j=1;j<=n;++j) printf("%d ",a[j]); printf("\n");
				}
				return ;
			}
		printf("No\n");
	}
	void solve() {
		if(B==1) {
			swap(A,B);
			for(int i=1;i<=n;++i) c[i]=1-c[i];
			solve(1);
		} else solve(0);
	}
}
int main()
{
	//usefile("array");
	int i; char ch;
	read(T);
	loop : --T;
	read(n,A,B);
	do ch=gc(); while(ch!='a'&&ch!='b');
	for(i=1;i<=n;++i) c[i]=ch=='b',ch=gc();
	if(n<=3) taskBF::solve();
	else taskA1::solve();
	if(T) goto loop;
	return 0;
}
0