QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150751 | #5434. Binary Substrings | TadijaSebez | ML | 24ms | 14872kb | C++14 | 1.7kb | 2023-08-26 07:33:32 | 2023-08-26 07:33:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=400050;
vector<int> E[N];
int ptr[N];
vector<int> cyc;
void DFS(int u){
while(true){
if(ptr[u]==E[u].size()){
cyc.pb(u);
return;
}
DFS(E[u][ptr[u]++]);
}
}
void Euler(int sz){
for(int mask=0;mask<(1<<sz);mask++){
E[mask].pb(mask>>1);
E[mask].pb((mask>>1)|(1<<(sz-1)));
}
DFS(0);
}
string Solve(int sz,int n){
vector<int> ord;
vector<int> next(1<<sz,0);
for(int i=0;i+1<cyc.size();i++){
ord.pb((cyc[i]<<1)|(cyc[i+1]&1));
}
for(int i=0;i<ord.size();i++){
next[ord[i]]=ord[(i+1)%ord.size()];
}
vector<int> p(1<<sz,0);
for(int mask=0;mask<(1<<sz);mask++){
p[mask]=next[mask]^1;
}
vector<bool> was(1<<sz,false);
vector<int> sol;
n-=1<<sz;
n-=sz-1;
for(int i=0;i<(1<<sz);i++){
int mask=ord[i];
sol.pb(mask);
if(!was[mask] && n>0){
while(!was[mask]){
was[mask]=true;
sol.pb(p[mask]);
mask=p[mask];
n--;
if(n==0)break;
}
}
}
string ans="";
for(int i=0;i<sz-1;i++){
ans+='0'+(sol[0]>>(sz-1-i)&1);
}
for(int mask:sol){
ans+='0'+(mask&1);
}
return ans;
}
void Brute(int n){
int ans=0;
string best="";
for(int mask=0;mask<(1<<n);mask++){
string now="";
for(int i=0;i<n;i++){
now+='0'+(mask>>i&1);
}
set<string> sub;
for(int l=0;l<n;l++){
for(int r=l;r<n;r++){
sub.insert(now.substr(l,r-l+1));
}
}
if(ans<sub.size()){
ans=sub.size();
best=now;
}
}
printf("%s\n",best.c_str());
}
int main(){
int n;
scanf("%i",&n);
if(n<=N){
Brute(n);
return 0;
}
int sz=1;
while((1<<(sz+1))+sz<=n)sz++;
Euler(sz-1);
string ans=Solve(sz,n);
printf("%s\n",ans.c_str());
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 14872kb
input:
2
output:
10
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 14260kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 13100kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 14844kb
input:
3
output:
100
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 1ms
memory: 14720kb
input:
4
output:
0100
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 1ms
memory: 14224kb
input:
6
output:
011000
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 3ms
memory: 14644kb
input:
7
output:
1101000
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 4ms
memory: 13772kb
input:
8
output:
01101000
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 4ms
memory: 14256kb
input:
9
output:
001101000
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 3ms
memory: 13356kb
input:
10
output:
0011101000
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 9ms
memory: 13888kb
input:
11
output:
00111010000
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 24ms
memory: 13136kb
input:
12
output:
101110010000
result:
ok meet maximum 59
Test #13:
score: -100
Memory Limit Exceeded
input:
200000