QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#315963#5434. Binary SubstringsNahidameowWA 0ms3880kbC++207.0kb2024-01-27 16:42:012024-01-27 16:42:02

Judging History

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

  • [2024-01-27 16:42:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-01-27 16:42:01]
  • 提交

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