QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211729#5434. Binary SubstringslmeowdnRE 2ms9272kbC++143.1kb2023-10-12 20:39:292023-10-12 20:39:30

Judging History

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

  • [2023-10-12 20:39:30]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:9272kb
  • [2023-10-12 20:39:29]
  • 提交

answer

//vanitas vanitatum et omnia
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128; 
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}      
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii; 
typedef vector<int> vi;  
typedef vector<pii> vp; 
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=2e5+5;
int n,k,hd[N],s[N],nxt[N];
vi e[N],res,ans;

void dfs(int u) {
  //cout<<"DD "<<u<<endl;
  for(;hd[u]<s[u];) {
    int v=e[u][hd[u]]; hd[u]++;
    dfs(v); res.eb(u);
  }
}

signed main() {
  n=read();
  if(n==1) return puts("0"), 0;
  else if(n==2) return puts("01"), 0;
  else if(n==3) return puts("001"), 0;
  else if(n==4) return puts("0011"), 0;
  while(k+(1<<k)-1<=n) k++; k--;
  rep(i,0,(1<<k-1)-1) {
    e[i].eb(i>>1), e[i].eb((i>>1)|(1<<k-2));
  }
  rep(i,0,(1<<k-1)-1) hd[i]=0, s[i]=e[i].size();
  dfs(0);
  reverse(res.begin(),res.end());
  //for(int x:res) cout<<x<<" "; puts("");
  rep(i,0,(1<<k)-1) {
    int x=i, y=(x+1)%(1<<k), z=(y+1)%(1<<k);
    int u=res[x]|(res[y]<<1), v=res[y]|(res[z]<<1);
    //cout<<x<<" "<<y<<" "<<z<<" "<<u<<" "<<v<<endl;
    nxt[u]=v;
  }
  rep(i,0,(1<<k)-1) hd[i]=0, e[i].clear();
  rep(i,0,(1<<k)-1) {
    if((i>>1)!=nxt[i]) e[i].eb(i>>1);
    else e[i].eb((i>>1)|(1<<k-1));
  }
  rep(i,0,(1<<k)-1) s[i]=e[i].size();
  int rest=n-k+1-(1<<k), st=0, i=0;
  rep(t,0,(1<<k)-1) {
    res.clear(); if(hd[i]<s[i]) dfs(e[i][hd[i]]);
    reverse(res.begin(),res.end());
    //cout<<res.size()<<endl;
    if(res.size()>rest) {
      if(rest==0) {
        //cout<<"AA\n";
        //rep(j,t,(1<<k)-1) cout<<i<<" "<<(i>>(k-1))<<endl, ans.eb(i>>(k-1)), i=nxt[i];
      } else {
        vi p=ans; ans.clear(); int sz=res.size();
        st=res[sz-1-rest];
        rep(i,sz-1-rest,sz-2) ans.eb(res[i]>>(k-1));
        rep(j,t,(1<<k)-1) ans.eb(i>>(k-1)), i=nxt[i];
        ans.insert(ans.end(),p.begin(),p.end());
      }
      break;
    } else {
      rest-=res.size(); ans.eb(i>>(k-1));
      for(int x:res) ans.eb(x>>(k-1));
    }
    i=nxt[i];
  }
  rep(i,0,k-2) printf("%d",(st>>i)&1);
  rep(i,k-1,n-1) printf("%d",ans[i-(k-1)]);
  puts("");
  return 0; 
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9272kb

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

score: -100
Runtime Error

input:

5

output:


result: