QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211729 | #5434. Binary Substrings | lmeowdn | RE | 2ms | 9272kb | C++14 | 3.1kb | 2023-10-12 20:39:29 | 2023-10-12 20:39:30 |
Judging History
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