QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563412 | #5434. Binary Substrings | Wuyanru | WA | 2ms | 12852kb | C++14 | 1.9kb | 2024-09-14 11:26:54 | 2024-09-14 11:26:54 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
bool to[1000001][2];
char s[1000001];
int n,k,c;
void dfs(int num,int k)
{
int lim=(1<<k)-1;
if(!to[num][1])
{
to[num][1]=1;
dfs((num<<1|1)&lim,k);
s[c--]='1';
}
if(!to[num][0])
{
to[num][0]=1;
dfs((num<<1)&lim,k);
s[c--]='0';
}
}
inline int run(int p)
{
c=(2<<p)+p;
memset(s,'0',sizeof(s));s[c+1]=0;
memset(to,0,sizeof(to));to[0][0]=1;
dfs(0,p);
// printf("%s\n",s+1);
memset(to,0,sizeof(to));
int lim=(1<<(p+1))-1,lst=0,now=0;
for(int i=1;i<=(2<<p)+p;i++)
{
now=((now<<1)+s[i]-'0')&lim;
if(i>k) to[lst][s[i]-'0']=1;
lst=now;
// printf("i=%d now=%d\n",i,now);
}
// for(int i=0;i<=lim;i++) printf("%d : %d %d\n",i,to[i][0],to[i][1]);
return lst;
}
void output(int num,int now)
{
// printf("%d %d\n",num,now);
if(num==n+1)
{
s[n+1]=0;printf("%s\n",s+1);
exit(0);
}
for(int i=1;i>=0;i--) if(!to[now][i])
{
to[now][i]=1;s[num]=i+'0';
output(num+1,(now<<1|i)&((1<<k)-1));
to[now][i]=0;
}
}
int main()
{
n=read();
if(n==1){ printf("0\n");return 0;}
while(n>=(1<<(k+1))+k) k++;
// printf("k=%d\n",k);
output((1<<k)+k,run(k-1));
printf("wtf\n");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6640kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 6584kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 6652kb
input:
3
output:
011
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 1ms
memory: 6644kb
input:
4
output:
0110
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 0ms
memory: 6656kb
input:
6
output:
001101
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 1ms
memory: 6644kb
input:
7
output:
0011010
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 1ms
memory: 6652kb
input:
8
output:
00110100
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 0ms
memory: 6712kb
input:
9
output:
001101000
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 0ms
memory: 6588kb
input:
10
output:
0001110100
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 2ms
memory: 6712kb
input:
11
output:
00011101001
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 1ms
memory: 6664kb
input:
12
output:
000111010010
result:
ok meet maximum 59
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 12852kb
input:
200000
output:
wtf
result:
wrong answer Token parameter [name=s] equals to "wtf", doesn't correspond to pattern "[01]{200000}"