QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403060 | #5434. Binary Substrings | wangif424 | WA | 3ms | 34864kb | C++23 | 4.0kb | 2024-05-01 20:08:42 | 2024-05-01 20:08:46 |
Judging History
answer
#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
//#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
if (x<0)x=-x,push('-');
int sta[35],top=0;
do {
sta[top++]=x%10,x/=10;
} while (x);
while(top)push(sta[--top]^'0');
}
//#ifndef LOCAL
// char buf[1<<23],*p1=buf,*p2=buf;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//#endif
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
int n,k;
constexpr int N=1<<20;
struct edge{
int to,nxt=-1;
}v[N];
int len,fir[N];
void add(int x,int y){
++len;
v[len].to=y;
v[len].nxt=fir[x];
fir[x]=len;
}
int vis[N];
int ola[N],siz;
int mhd[N],tot,nxt[N],pre[N];
void dfo(int u){
// cout << u << '\n';
for(int i=fir[u];i!=-1;i=v[i].nxt){
// cerr << vis[i] << '|';
if(vis[i])continue;
vis[i]=1;
dfo(v[i].to);
}
ola[++siz]=u;
}
int num;
int dfn[N],low[N],cnt,ks,id[N],s[N],sy[N];
stack<int> st;
void dfs(int u){
// cerr << '{' << u;
low[u]=dfn[u]=++cnt;
vis[u]=1;
st.push(u);
for(int i=fir[u];i;i=v[i].nxt){
if(vis[v[i].to])low[u]=min(dfn[v[i].to],low[u]);
else if(!dfn[v[i].to]){
dfs(v[i].to);
low[u]=min(low[u],low[v[i].to]);
}
}
if(dfn[u]==low[u]){
++ks;
while(st.top()^u){
id[st.top()]=ks;
vis[st.top()]=0;
st.pop();
}
id[u]=ks;
sy[id[u]]=u;
st.pop();
vis[u]=0;
}
}
int chs[N];
int to[N];
signed main(){
// freopen("1.txt","w",stdout);
memset(fir,-1,sizeof(fir));
R(n);
if(n==1)return write(1),0;
else if(n==4)return write(1001),0;
int l=1,rr=n;
while(l<rr){
int mid=(l+rr+1)>>1;
if(mid<=1.0*log2(n*1.0+1-mid))l=mid;
else rr=mid-1;
}
k=l-1;
for(int i=0;i<(1<<k);i++){
add(i,(i<<1)&((1<<k)-1));
add(i,((i<<1)&((1<<k)-1))+1);
}
dfo(0);
// return 0;
for(int i=1;i<=siz/2;i++)swap(ola[i],ola[siz-i+1]);
tot=(1<<(k+1));
for(int i=1;i<=tot;i++){
mhd[i]=(ola[i]<<1)|ola[i+1];
// cerr << mhd[i] << ' ';
}
// cerr << '\n';
memset(vis, 0,sizeof(vis));
memset(fir,-1,sizeof(fir));
for(int i=1;i<=len;i++)v[i].nxt=-1;
// cerr << tot << '\n';
for(int i=1;i<=tot;i++){
nxt[mhd[i]]=mhd[i==tot?1:i+1];
// cerr << mhd[i] << ' ' << nxt[mhd[i]] << '\n';
}
k++;
for(int i=0;i<(1<<k);i++){
// cerr << "{" << i << ' ' <<((i<<1)&((1<<k)-1)) << ' ' <<nxt[i] << '\n';
if(((i<<1)&((1<<k)-1))==nxt[i]){
add(i,((i<<1)&((1<<k)-1))+1);
to[i]=((i<<1)&((1<<k)-1))+1;
}else{
add(i,(i<<1)&((1<<k)-1));
to[i]=((i<<1)&((1<<k)-1));
}
// cerr << i << ' ' << to[i] << '\n';
}
num=n-(tot+k-1);
for(int i=1;i<=tot;i++)if(!dfn[mhd[i]])dfs(mhd[i]);
for(int i=1;i<=tot;i++)s[id[mhd[i]]]++;
// for(int i=1;i<=tot;i++)cerr << id[mhd[i]] << ' ';
// cerr<<'\n' << num;
int st=nxt[sy[0]],th=0;
for(int i=1;i<=ks;i++){
if(num>=s[i]&&chs[i]==0){
num-=s[i];
chs[i]=1;
// cerr << ':' << sy[i] << ' ' << i << '\n';
}
else{
chs[i]=2;
th=i;
st=nxt[sy[th]];
break;
}
}
// for(int i=1;i<=ks;i++)cerr << chs[i];
// cerr<<'\n';
int b=st>>1,c=0;
for(int i=1;i<k;i++){
c=(c<<1)|(b&1);
b>>=1;
}
for(int i=1;i<k;i++){
write(c&1);
c>>=1;
}
// return 0;
for(int i=st;i!=sy[th];i=nxt[i]){
// cerr << '|'<<i <<'\n';
write(i&1);//cerr<<(i&1);
if(chs[id[i]]==1){
// cerr << id[i] << ' ' << chs[id[i]] << '\n';
// push('(');
chs[id[i]]=0;
// cerr << sy[id[i]] << '\n';
// cerr << ;
for(int u=to[i],tep=s[id[i]];tep>0;tep--,u=to[u]){
write(u&1);
// cerr << u << '\n';
}
// push(')');
}
}
// cerr << sy[th] << ' ' << nxt[sy[th]];
write(sy[th]&1);
for(int u=to[sy[th]];num>0;num--,u=to[u]){
write(u&1);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 34492kb
input:
2
output:
10
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 34864kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 19932kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 32852kb
input:
3
output:
001
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 0ms
memory: 20124kb
input:
4
output:
1001
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 32376kb
input:
6
output:
110001
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 3ms
memory: 32280kb
input:
7
output:
1100010
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 32380kb
input:
8
output:
10100011
result:
ok meet maximum 27
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 32516kb
input:
9
output:
01011100
result:
wrong answer Token parameter [name=s] equals to "01011100", doesn't correspond to pattern "[01]{9}"