Submission #48213283

---

Source Code Expand

// LUOGU_RID: 138328813
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)

#ifdef EXODUS
	#define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
	#define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
	x=0;T flg=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=flg;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;

constexpr int N=57;
int n;char s[N],t[N];
ll f[N][(1<<18)+7],trs[(1<<18)+7][2][2];

bool memed=0;

//=========================================================================================================
// Code here.

void solve(){
	read(n);scanf("%s%s",s+1,t+1);
	auto shift=[&](int x){return 1ll<<x;};
	auto chk=[&](ll &x,ll y){if(x<y)x=y;};
	int lim=(n-1)/3+2,full=shift(lim);
	for(int S=1;S<full;S++){
		int mxb=__lg(S);int _0=mxb-1,_1=mxb-1;
		while(_0>=0&&(S&shift(_0)))_0--;while(_1>=0&&!(S&shift(_1)))_1--;
		if(_0>=0)trs[S][0][0]=((S&(shift(_0)-1))|shift(_0))<<1,trs[S][0][1]=((S&(shift(_0)-1))|shift(_0))<<1|1;
		if(_1>=0)trs[S][1][0]=((S&(shift(_1)-1))|shift(_1))<<1,trs[S][1][1]=((S&(shift(_1)-1))|shift(_1))<<1|1;
		// printf("%lld %lld %lld %lld\n",trs[S][0][0],trs[S][0][1],trs[S][1][0],trs[S][1][1]);
	}
	f[1][1]=1;
	for(int i=1;i<=n;i++){
		int sn=(s[i]=='X'),tn=(t[i]=='X');
		for(int S=1;S<full;S++){
			if(!f[i][S])continue;
			if(sn==tn)chk(f[i+1][1],(f[i][S]<<1)|sn);
			if(S<shift(lim-1))chk(f[i+1][(S<<1)|sn],f[i][S]),chk(f[i+1][(S<<1)|tn],f[i][S]);
			if(trs[S][sn][tn])chk(f[i+1][trs[S][sn][tn]],(f[i][S]<<1)|sn);
			if(trs[S][tn][sn])chk(f[i+1][trs[S][tn][sn]],(f[i][S]<<1)|tn);
		}
	}
	ll ans=1;
	for(int S=1;S<full;S++)chk(ans,f[n+1][S]);
	for(int i=__lg(ans)-1;i>=0;i--)
		printf("%c",(ans&shift(i))?'X':'Y');
	printf("\n");
	return;
}


//=========================================================================================================

int main(){
	Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
	int timbg=clock();
	int T=1;
	while(T--)solve();
	int timed=clock();
	Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
	fflush(stdout);
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:56:17: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
   56 |                 while(_0>=0&&(S&shift(_0)))_0--;while(_1>=0&&!(S&shift(_1)))_1--;
      |                 ^~~~~
Main.cpp:56:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
   56 |                 while(_0>=0&&(S&shift(_0)))_0--;while(_1>=0&&!(S&shift(_1)))_1--;
      |                                                 ^~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:18:28: warning: statement has no effect [-Wunused-value]
   18 |         #define Debug(...) 0
      |                            ^
Main.cpp:84:9: note: in expansion of macro ‘Debug’
   84 |         Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
      |         ^~~~~
Main.cpp:18:28: warning: statement has no effect [-Wunused-value]
   18 |         #define Debug(...) 0
      |                            ^
Main.cpp:89:9: note: in expansion of macro ‘Debug’
   89 |         Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
      |         ^~~~~
Main.cpp:85:13: warning: unused variable ‘timbg’ [-Wunused-variable]
   85 |         int timbg=clock();
      |             ^~~~~
Main.cpp:88:13: warning: unused variable ‘timed’ [-Wunused-variable]
   88 |         int timed=clock();
      |             ^~~~~
Main.cpp: In function ‘void solve()’:
Main.cpp:50:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         read(n);scanf("%s%s",s+1,t+1);
      |                 ~~~~~^~~~~~~~~~~~~~~~

Judge Result