QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403045 | #5434. Binary Substrings | wangif424 | RE | 16ms | 41260kb | C++23 | 4.1kb | 2024-05-01 19:52:13 | 2024-05-01 19:52:15 |
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||n==9){
switch(n){
case 1:{
push('1');
break;
}
case 2:{
write(10);
break;
}
case 3:{
write(101);
break;
}
case 4:{
write(1001);
break;
}
case 9:{
push('0');
write(11101000);
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++;
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: 0ms
memory: 19964kb
input:
2
output:
10
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 34492kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 3ms
memory: 17960kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 17988kb
input:
3
output:
101
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 0ms
memory: 18324kb
input:
4
output:
1001
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 32612kb
input:
6
output:
110001
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 0ms
memory: 32244kb
input:
7
output:
1100010
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 32448kb
input:
8
output:
10100011
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 0ms
memory: 20132kb
input:
9
output:
011101000
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 0ms
memory: 34492kb
input:
10
output:
0011101000
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 0ms
memory: 32272kb
input:
11
output:
01110100001
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 3ms
memory: 32272kb
input:
12
output:
011101000010
result:
ok meet maximum 59
Test #13:
score: 0
Accepted
time: 16ms
memory: 41260kb
input:
200000
output:
111111100111111110000001010000000111111101100000010000001100111111011111101010000011000000101000001011111110101111111000000011100000010000001000111111011111100010000011000000111011111001111110001000010100000011101111010111111000100001110000001110111100011111100010001001000000111011101111111110001001...
result:
ok meet maximum 19996962278
Test #14:
score: 0
Accepted
time: 3ms
memory: 32344kb
input:
24
output:
001111011001010000010011
result:
ok meet maximum 240
Test #15:
score: -100
Runtime Error
input:
35