QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287282#7967. 二进制one_god_and_two_dogsML 28ms212800kbC++171.9kb2023-12-20 10:07:312023-12-20 10:07:31

Judging History

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

  • [2023-12-20 10:07:31]
  • 评测
  • 测评结果:ML
  • 用时:28ms
  • 内存:212800kb
  • [2023-12-20 10:07:31]
  • 提交

answer

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

const int M=(1<<22)+10;
struct BIT{
	int f[M];
	void upd(int x,int v){
		while(x<M)f[x]+=v,x+=x&-x;
	}
	int qry(int x){
		int res=0;
		while(x)res+=f[x],x-=x&-x;
		return res;
	}
}Tr;

char str[M];	
int len[M],nxt[M],pre[M],n;

int getnxt(int x){
	return nxt[x]==x?x:nxt[x]=getnxt(nxt[x]);
}
int getpre(int x){
	return pre[x]==x?x:pre[x]=getpre(pre[x]);
}
set<int>s[M];
void rebuild(int op){
	int cnt=0,now=0;
	for(int i=n;i;--i){
		if(pre[i]==i){
			cnt++;
			now=now>>1;
			if(str[i])now+=1<<(op-1);
			if(cnt>=op&&len[now]==op)
				s[now].insert(i);
		}
	}
}


int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>str;
	for(int i=n;i;--i)str[i]=str[i-1]-'0';
	for(int i=1;i<=n;++i)len[i]=len[i>>1]+1;
	for(int i=1;i<=n+1;++i)nxt[i]=pre[i]=i;
	for(int i=1;i<=n;++i)Tr.upd(i,1);
	int tot=n;
	for(int i=1;i<=n;++i){
		if(len[i]!=len[i-1])rebuild(len[i]);
		if(!s[i].empty()){
			int t=*s[i].begin();
			cout<<Tr.qry(t)<<" "<<s[i].size()<<"\n";
			//erase
			int now=i;
			s[now].erase(t);
			for(int c=1,j=getnxt(t+len[i]);c<len[i]&&j<=n;++c,j=getnxt(j+1)){
				now=now<<1&((1<<len[i])-1);
				if(str[j])now|=1;
				if(len[now]==len[i])s[now].erase(t+c);
			}
			now=i;
			for(int c=1,j=getpre(t-1);c<len[i]&&j;++c,j=getpre(j-1)){
				now=now>>1;
				if(str[j])now|=1<<(len[i]-1);
				if(len[now]==len[i])s[now].erase(j);
			}

			for(int c=0,j=t;c<len[i];++c,j=getnxt(j+1))
				pre[j]=j-1,nxt[j]=j+1,Tr.upd(j,-1);
			tot-=len[i];

			//insert
			int l=t;
			for(int c=1;c<len[i]&&getpre(l-1);c++,l=getpre(l-1));
			int r=l;
			
			now=0;
			for(int c=1;c<len[i]&&r<=n;++c,r=getnxt(r+1)){
				now=now<<1&((1<<len[i])-1);
				if(str[r])now|=1;
			}

			for(int c=1;c<len[i]&&r<=n&&l<t;++c,r=getnxt(r+1),l=getnxt(l+1)){
				now=now<<1&((1<<len[i])-1);
				if(str[r])now|=1;
				if(len[now]==len[i])s[now].insert(l);
			}
	//		for(int i=4;i<=6;++i){
	//			for(int x:s[i])cout<<x<<" ";
	//		}
	//		cout<<"---"<<endl;;
		}else cout<<"-1 0\n";
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 28ms
memory: 212800kb

input:

20
01001101101101110010

output:

2 11
5 5
4 5
11 1
4 2
7 1
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0

result:

ok 20 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

1000000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1 1000000
-1 0
1 999998
-1 0
-1 0
-1 0
1 999995
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
1 999991
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
1 999986
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0...

result: