QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#450465#1289. A + B Problemdrowsylve_233TL 1ms7864kbC++144.0kb2024-06-22 13:47:152024-06-22 13:47:15

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 13:47:15]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:7864kb
  • [2024-06-22 13:47:15]
  • 提交

answer

bool M1;
#include<bits/stdc++.h>
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr<<(clock()-ST)*1.0/CLOCKS_PER_SEC<<'\n'
//#define int long long
using namespace std;
const int N=1000005;
int T0,n,m;
string s;
int a[N];
/*
inline int qpow(int x,int p){
	int res=1;
	while(p){
		if(p&1) res=res*x;
		x=x*x;
		p>>=1;
	}
	return res;
}
void to2(int x){
	if(!x){cout<<0<<'\n';return;} 
	int q[21],tq=0;
	while(x){
		if(x&1) q[++tq]=1;
		else q[++tq]=0;
		x>>=1;
	}
	for(int i=tq;i>=1;i--) cout<<q[i];
	cout<<'\n';
}
int f[505][505];//A:pick-j
void solve1(){
	for(int i=1;i<=n+m+1;i++) for(int j=0;j<=n;j++) f[i][j]=0;
	for(int i=n+m,iq=1;i>=1;i--,iq++){
		for(int j=0;j<=min(n,iq);j++){
			if(a[i]){
				if(j==0) f[i][j]=f[i+1][j]+qpow(2,iq-1);
				else{
					if(j==iq) f[i][j]=f[i+1][j-1]+qpow(2,j-1);
					else f[i][j]=max(f[i+1][j]+qpow(2,iq-j-1),f[i+1][j-1]+qpow(2,j-1));
				}
			}else{
				if(j==0) f[i][j]=f[i+1][j];
				else f[i][j]=max(f[i+1][j],f[i+1][j-1]);
			}
		}
	}
	to2(f[1][n]);
//	cout<<f[1][n]<<'\n';
}
*/
int rt[2005][2005];
const int N2=5e7;
int R;
int fn[4005],tf,hv1;
struct segtree{
	struct node{
		int ls,rs,t,h;
	}c[N2+5];
	int tot;
	void mdf(int l,int r,int &p,int p0,int x){//使用时整体偏移了一位,2^0-->2^1 
		c[p=++tot]=c[p0];
		c[p].t++;
		if(l==r) return;
		int mid=l+r>>1;
		if(x<=mid) mdf(l,mid,c[p].ls,c[p0].ls,x);
		else mdf(mid+1,r,c[p].rs,c[p0].rs,x);
	}
	int qry(int l,int r,int px,int py,int dtx,int dty){
		if(l==r){
			int xx=c[px].t;
			if(dtx==l) xx++;
			int yy=c[py].t;
			if(dty==l) yy++;
			if(xx<yy) return 0;
			if(xx==yy) return 1;
			return 2;
		}
		int mid=l+r>>1;
		if(dtx<=mid && dty<=mid && c[c[px].rs].t==0 && c[c[py].rs].t==0)
			return qry(l,mid,c[px].ls,c[py].ls,dtx,dty);
		int cmp=qry(mid+1,r,c[px].rs,c[py].rs,dtx,dty);
		if(cmp!=1) return cmp;
		int cmpl=qry(l,mid,c[px].ls,c[py].ls,dtx,dty);
		return cmpl;
	}
	void jw(int l,int r,int p){
		if(l==r){
			fn[++tf]=c[p].t;
			if(c[p].t) hv1=1;
			return;
		}
		int mid=l+r>>1;
		jw(l,mid,c[p].ls);
		jw(mid+1,r,c[p].rs);
	}
}T;
void clean(){
	for(int i=1;i<=n+m+1;i++) for(int j=0;j<=n;j++) rt[i][j]=0;
	for(int i=0;i<=T.tot;i++) T.c[i].ls=T.c[i].rs=T.c[i].t=0;
	T.tot=0;
}
void solve2(){
//	for(int i=1;i<=n+m;i++) for(int j=0;j<=n;j++) rt[i][j]=++tot;
//	clear! T.tot=0;
	for(int i=n+m,iq=1;i>=1;i--,iq++){
		int lim=min(n,iq);
		for(int j=0;j<=lim;j++){
			if(a[i]){
				if(j==0) T.mdf(1,R,rt[i][j],rt[i+1][j],iq);
				else{
					if(j==iq) T.mdf(1,R,rt[i][j],rt[i+1][j-1],j);
					else{//left更大 return 12 
						int cmp=T.qry(1,R,rt[i+1][j],rt[i+1][j-1],iq-j,j);
						if(cmp>=1) T.mdf(1,R,rt[i][j],rt[i+1][j],iq-j);
						else T.mdf(1,R,rt[i][j],rt[i+1][j-1],j);
					}
				}
			}else{
				if(j==0) rt[i][j]=rt[i+1][j];
				else{
					int cmp=T.qry(1,R,rt[i+1][j],rt[i+1][j-1],0,0);
					if(cmp>=1) rt[i][j]=rt[i+1][j];
					else rt[i][j]=rt[i+1][j-1];
				}
			}
		}
	}
	hv1=0,tf=0;
	T.jw(1,R,rt[1][n]);
	if(hv1==0){
		cout<<"0\n";
		clean();
		return;
	}
	for(int i=1;i<=tf;i++){
		if(fn[i]==0||fn[i]==1) continue;
		fn[i+1]+=fn[i]/2;
		fn[i]=(fn[i]&1);
	}
	int num=fn[tf+1];
	while(num){
		fn[++tf]=(num&1);
		num/=2;
	}
	bool prex=0;
	for(int i=tf;i>=1;i--){
		if(fn[i]){
			prex=1;
			cout<<1;
		}else if(prex){
			cout<<0; 
		}
	}
	cout<<'\n';
	clean();
}
/*
1
6 4
1110001011
*/
bool M2;
signed main(){
//	fc example2.out partition.out
//	look_memory;
//	freopen("example2.in","r",stdin);
//	freopen("partition.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T0;
	while(T0--){
		cin>>n>>m>>s;
		if(n<m) swap(n,m);
		s="#"+s;
		for(int i=1;i<=n+m;i++) a[i]=(s[i]=='1');
//		if(n<=10&&m<=10){solve1();continue;}
		if(n<=500&&m<=500){R=500;solve2();continue;}
		if(n<=2000&&m<=2000){R=n+m;solve2();continue;}
	}
	return 0;
}
/*
3
1 3
0110
3 3
100011
1 2
000

110
111
0
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7864kb

input:

3
4 3
1000101
2 2
1111
1 1
00

output:

1101
110
0

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

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: