QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287282 | #7967. 二进制 | one_god_and_two_dogs | ML | 28ms | 212800kb | C++17 | 1.9kb | 2023-12-20 10:07:31 | 2023-12-20 10:07:31 |
Judging History
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...