QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#315963 | #5434. Binary Substrings | Nahidameow | WA | 0ms | 3880kb | C++20 | 7.0kb | 2024-01-27 16:42:01 | 2024-01-27 16:42:02 |
Judging History
answer
#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Math{
ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
//=========================================================
namespace IO{
const double eps=1e-8;
const int BUFSIZE=1<<20;
char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
char tmp[BUFSIZE];int cnt=0;
inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}
ul readUll(){ul x=0;char c=0;while(!isdigit(c))c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return x;}
void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
void putString(std::string x){for(auto p:x)putch(p);}
void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}
void putUll(ul x){char Q[25];int tp=0;if(!x)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
struct Basic{
Basic &operator>>(int &A){A=IO::readInt();return (*this);}
Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
Basic &operator>>(char &A){A=IO::readChar();return (*this);}
Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
template<typename T1,typename T2>
Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
template<typename T,int d>
Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
template<typename T>
Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}
Basic &operator>>(ul &v){v=readUll();return (*this);}
Basic &operator<<(const int &A){putint(A);return (*this);}
Basic &operator<<(const char &A){putch(A);return (*this);}
Basic &operator<<(const ll &A){putLL(A);return (*this);}
Basic &operator<<(const Int &A){putInt128(A);return (*this);}
Basic &operator<<(const std::string &A){putString(A);return (*this);}
Basic &operator<<(const LD &A){putDouble(A);return (*this);}
Basic &operator<<(const double &A){putDouble(A);return (*this);}
Basic &operator<<(const float &A){putDouble(A);return (*this);}
template<typename T>
Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}
Basic &operator<<(const ul &A){putUll(A);return (*this);}
void Flush(){flush();}
}cin,cout;
}
//=========================================================
bool FileIfstream(std::string name){
std::ifstream f(name.c_str());
return f.good();
}
//=========================================================
//const int mod=998244353;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
//void add(int &x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}
const int N=2e5+10;
void solve(){
//don't forget to open long long
int n;IO::cin>>n;
if(n==1)return IO::cout<<"0\n",void();
if(n==2)return IO::cout<<"01\n",void();
if(n==3)return IO::cout<<"010\n",void();
if(n==4)return IO::cout<<"0010\n",void();
int lim=0;for(;(1<<lim)+lim-1<=n;lim++);--lim;
std::vector<int>cir;std::vector<bool>vis(n);int S=(1<<lim);
auto dfs=[&](int x,auto self)->bool{
int to;
vis[x]=1;cir.pd(x);if(cir.size()==S)return true;
to=(x<<1)%S;
if(!vis[to]&&self(to,self))return true;
to=(x<<1|1)%S;
if(!vis[to]&&self(to,self))return true;
vis[x]=false;cir.pop_back();
return false;
};
assert(dfs(0,dfs));
std::vector<int>nxt(S+1);
for(int i=0;i<S;i++)
for(int j=0;j<2;j++)
if((cir[i]<<1|j)%S==cir[(i+1)%S])
nxt[cir[i]]=(cir[i]<<1|j)%S;
int R=(n-(S+lim-1)),pos,rp;
std::vector<int>vt(S+1),to(S+1);
for(int i=0;i<S;i++)
if(!to[i]){
int sz=0;
for(int p=i;!to[p];p=nxt[p])to[p]=1,++sz;
if(sz>R){rp=i;break;}
else vt[i]=1,R-=sz;
}
for(int i=0;i<S;i++)if(cir[i]==rp){pos=i+1;break;}
std::vector<int>ans;
// IO::cout<<cir;
for(int i=0;i<S;i++){
ans.pd(cir[(pos+i-2+1)%S]);
if(vt[ans.back()]){
int R=ans.back(),S=ans.back();
do{R=nxt[R];ans.pd(R);}while(R^S);
}
}
R=rp;while(ans.size()+lim-1<n)ans.pd(R),R=nxt[R];
for(int i=lim-1;~i;i--)IO::cout<<(ans[0]>>i&1);
for(int i=1;i<ans.size();i++)IO::cout<<(ans[i]&1);
IO::cout<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
if(!FileIfstream("IO.in")){
freopen("IO.in","w",stdout);
return 0;
}
freopen("IO.in","r",stdin);
freopen("IO.out","w",stdout);
#endif
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
//std::cout.tie(0);
int T=1;
while(T--)solve();
IO::cout.Flush();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3
output:
010
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4
output:
0010
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
6
output:
001100
result:
ok meet maximum 16
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3644kb
input:
7
output:
0011001
result:
wrong answer not meet maximum 20 < 21