QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#450465 | #1289. A + B Problem | drowsylve_233 | TL | 1ms | 7864kb | C++14 | 4.0kb | 2024-06-22 13:47:15 | 2024-06-22 13:47:15 |
Judging History
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...