QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305862 | #5434. Binary Substrings | ELDRVD | WA | 1ms | 5772kb | C++14 | 2.0kb | 2024-01-16 05:05:40 | 2024-01-16 05:05:41 |
Judging History
answer
//https://qoj.ac/contest/1096/problem/5434?v=1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"
#define all(data) data.begin(),data.end()
#define TYPEMAX(type) std::numeric_limits<type>::max()
#define TYPEMIN(type) std::numeric_limits<type>::min()
#define MAXN 1000007
ll p[MAXN],nxt[MAXN],cnt,k;
bool vis[MAXN];
void DFS(ll i)
{
vis[i]=true;
if(!vis[i*2%(1<<k)]) DFS(i*2%(1<<k));
if(!vis[(i*2+1)%(1<<k)]) DFS((i*2+1)%(1<<k));
p[++cnt]=i;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
ll n; cin>>n;
if(n==1) {cout<<1<<endl; return 0;}
while((1<<k)+k<=n+1) k++;
k--; DFS(0);
ll ii=1,jj=cnt;
while(ii<jj) swap(p[ii++],p[jj--]);
if(n==(1<<k)+k-1)
{
for(int i=1;i<k;i++) cout<<0;
for(int i=1;i<=cnt;i++) cout<<(p[i]&1);
return 0;
}
for(int i=0;i<(1<<(k+1));i++) {vis[i]=0; nxt[i]=-1;}
for(int i=1;i<=cnt;i++)
{
p[i]=(p[i]<<1)|(p[i+1]&1);
vis[p[i]]=true;
}
for(int i=1;i<=cnt;i++) nxt[p[i]]=p[i%cnt+1];
for(int i=0;i<(1<<(k+1));i++)
{
if(nxt[i]<0) nxt[i]=nxt[i^(1<<k)]^1;
}
for(int i=0;i<(1<<(k+1));i++)
{
if(!vis[i])
{
ii=i; swap(nxt[i],nxt[i^(1<<k)]);
while(!vis[ii]) {cnt++; vis[ii]=true;}
if(cnt+k>=n)
{
for(int j=k;j+1;j--) cout<<((nxt[i]>>j)&1);
jj=nxt[nxt[i]];
for(int j=k+2;j<=n;j++) {cout<<(jj&1); jj=nxt[jj];}
break;
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5720kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 5712kb
input:
5
output:
00110
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
1
output:
1
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 5768kb
input:
3
output:
010
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
4
output:
0100
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
6
output:
001100
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
7
output:
0011000
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
8
output:
10001101
result:
ok meet maximum 27
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 5636kb
input:
9
output:
011011011
result:
wrong answer not meet maximum 23 < 34