QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403039 | #5434. Binary Substrings | wangif424 | RE | 5ms | 20176kb | C++23 | 4.1kb | 2024-05-01 19:46:45 | 2024-05-01 19:47:03 |
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<5){
switch(n){
case 1:{
push('1');
break;
}
case 2:{
write(10);
break;
}
case 3:{
write(101);
break;
}
case 4:{
write(1001);
break;
}
}
return 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];
memset(vis, 0,sizeof(vis));
memset(fir,-1,sizeof(fir));
for(int i=1;i<=len;i++)v[i].nxt=-1;
for(int i=1;i<=tot;i++){
nxt[mhd[i]]=mhd[i==tot?1:i+1];
}
k++;
// cerr << "||" << nxt[7];
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 r,st,th;
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]];
r=i;
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;
}
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);
// push(' ');
for(int u=to[sy[th]];num>0;num--,u=to[u]){
write(u&1);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 15824kb
input:
2
output:
10
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 20176kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 16040kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 15832kb
input:
3
output:
101
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 2ms
memory: 16044kb
input:
4
output:
1001
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 4ms
memory: 20068kb
input:
6
output:
110001
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 0ms
memory: 20028kb
input:
7
output:
1100010
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 3ms
memory: 20040kb
input:
8
output:
10100011
result:
ok meet maximum 27
Test #9:
score: -100
Runtime Error
input:
9