QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#831239#1289. A + B ProblemlyxWA 448ms22964kbC++142.6kb2024-12-25 12:09:022024-12-25 12:09:03

Judging History

This is the latest submission verdict.

  • [2024-12-25 12:09:03]
  • Judged
  • Verdict: WA
  • Time: 448ms
  • Memory: 22964kb
  • [2024-12-25 12:09:02]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e6+5;
int T,n,m,a[2][N],k[2],la[N],ar[N],b[N],ans[N];
int jl[2][N];
inline void air(){}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
inline int read(){
	register char ch=getchar();
	while(ch<'0'||ch>'1')ch=getchar();
	return ch-'0';
}
inline int bj(){
	if(jl[0][0]>jl[1][0]){
		return 1;
	}
	if(jl[0][0]<jl[1][0])return 0;
	fd(i,b[0],1){
		if(jl[0][i]>jl[1][i]){
			return 1;
		}
		if(jl[0][i]<jl[1][i])return 0;
	}
	return 2;
}
inline void get(){
	ans[0]=b[0];
	fo(i,1,b[0])ans[i]=b[i];
}
inline void upd(){
	if(b[0]>ans[0]){
		get();
		return;
	}
	if(b[0]<ans[0])return;
	fd(i,b[0],1){
		if(b[i]>ans[i]){
			get();
			return;
		}
		if(b[i]<ans[i])return;
	}
}
inline void check(ri st,ri op){
	if(st>m)return;
	fo(i,1,max(n,m)+1)a[0][i]=a[1][i]=b[i]=0;
	k[0]=n;k[1]=m;
	fo(i,1,st)a[1][k[1]--]=ar[i];
	fo(i,st+1,n+m){
		if(!k[0])a[1][k[1]--]=ar[i];
		else if(!k[1])a[0][k[0]--]=ar[i];
		else{
			ri nw=k[1]>k[0];
			if(k[nw^1]>=la[i]-i){
				a[nw][k[nw]--]=1;
				fo(j,1,la[i]-i)a[nw^1][k[nw^1]--]=0;
				i=la[i];
			}
			else{
				a[nw][k[nw]--]=0;
			}
		}
	}
	fo(i,1,max(n,m)){
		b[i]+=a[0][i]+a[1][i];
		b[i+1]+=b[i]/2;b[i]&=1;
	}
	b[0]=1;
	fd(i,max(n,m)+1,1){
		if(b[i]){b[0]=i;break;}
	}
	fo(i,0,b[0])jl[op][i]=b[i];
	upd();
}
int main(){
	scanf("%d",&T);
//	ri js=0;
	while(T--){
		read(n);read(m);
		if(n<m)swap(n,m);
		fo(i,1,n+m){
			ar[i]=read();
		}
		ri La=n+m+1;la[n+m+1]=La;
		fd(i,n+m,1){
			if(ar[i])La=i;la[i]=La;
		}
		ans[0]=0;
//		++js;
//		if(js==218){
//			air();
//		}
		ri l=0,r=m;
		while(l<=r){
			ri md=l+r>>1;
			jl[0][0]=jl[1][0]=0;
			if(md>1)check(md-1,0);
			check(md+1,0);
			check(md,0);check(ar[md]?la[md+1]:la[md],1);
			ri o=bj();
			if(o==2){
				if(ar[md+1])l=md+1;
				else r=md-1;
			}
			else if(o){
				r=md-1;
			}
			else{
				l=md+1;
			}
		}
		fd(i,ans[0],1)putchar(ans[i]+'0');
		puts("");
	}
	cerr<<endl<<endl<<"time:"<<(double)clock()/CLOCKS_PER_SEC<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 20416kb

input:

3
4 3
1000101
2 2
1111
1 1
00

output:

1101
110
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 448ms
memory: 22964kb

input:

11110
10 8
111011010011100100
3 5
01011000
7 6
1110101010000
9 1
0110100101
1 9
0100001110
8 10
000101101011111000
9 6
011111111000111
1 9
1011101101
10 7
00100011000100000
4 9
1000101101010
8 4
100100110000
8 9
00101111011000101
8 9
11000000101011110
7 6
1111010100110
2 9
01001110101
4 5
100010100
...

output:

10011010100
11100
10101000
110100101
100001110
10000001100
1000010111
111101101
1110100000
111101010
11110000
1000011101
1001011110
10101110
101110101
11100
1111010
1000010
1011100010
10010101001
10010001
1001010
1000000010
1110
111
1111110001
10110111
1100010101
10000000
111000011
110
11111
1100101...

result:

wrong answer 6607th lines differ - expected: '10100001011', found: '10100001001'