QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305874 | #5434. Binary Substrings | NemanjaSo2005 | WA | 6ms | 44528kb | C++14 | 3.6kb | 2024-01-16 05:38:59 | 2024-01-16 05:38:59 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int N,M,K;
const int maxn=(1<<20)+5;
vector<int> graf[maxn];
int perm[maxn];
bool bio[maxn],uzmi[maxn];
priority_queue<pair<int,int>> PQ;
void getcycle(int x){
if(bio[x])
return;
int gde=x,s=0;
//cout<<"PRATIM "<<gde<<endl;
do {
s++;
bio[gde]=true;
// cout<<gde<<endl;
gde=perm[gde];
} while(gde!=x);
// cout<<"CIKLUS "<<s<<" "<<x<<endl;
PQ.push({s,x});
}
int count_substrings(string x) {
unordered_set<string> substrings;
// Iterate over all substrings
for (int i = 0; i < x.length(); ++i) {
string substring = "";
for (int j = i; j < x.length(); ++j) {
substring.push_back(x[j]);
substrings.insert(substring);
}
}
// Return the count of distinct substrings
return substrings.size();
}
void napravi(int k){
M=1<<(k-1);
for(int i=0;i<(1<<(k));i++){
int a=i>>1;
int b=i&((1<<(k-1))-1);
graf[a].push_back(b);
}
}
vector<int> V,R;
void poperm(int gde){
R.push_back(gde);
if(perm[gde]==0)
return;
int p=perm[gde];
perm[gde]=0;
poperm(p);
}
void euler(int gde){
while(graf[gde].size()){
int ko=graf[gde].back();
graf[gde].pop_back();
euler(ko);
}
V.push_back(gde);
}
signed main(){
cin>>N;
if(N==1){
cout<<"0\n";
return 0;
}
if(N==2){
cout<<"01\n";
return 0;
}
if(N==3){
cout<<"010\n";
return 0;
}
if(N==4){
cout<<"1001\n";
return 0;
}
for(int i=0;i<=20;i++){
if((1<<i)+i-1<=N)
K=i;
}
//cout<<"DUZINA JE "<<K<<endl;
napravi(K);
euler(0);
reverse(V.begin(),V.end());
/* cout<<"CIKLUS: ";
for(int i=0;i<V.size();i++)
cout<<V[i]<<" ";
cout<<endl;*/
string poc="";
if(((1<<(K))+K-1)!=N){
vector<int> B;
for(int i=1;i<V.size();i++)
B.push_back((V[i-1]<<1) + (V[i]&1));
/*
cout<<"NIZ B:"<<endl;
for(int i=0;i<B.size();i++)
cout<<B[i]<<" ";
cout<<endl;*/
B.push_back(B[0]);
for(int i=0;i+1<B.size();i++)
perm[B[i]]=B[i+1]^1;
/* cout<<"PERM"<<endl;
for(int i=0;i<B.size();i++)
cout<<perm[i]<<" ";
cout<<endl;*/
poc="";
for(int i=(1<<K);i>=2;i>>=1)
poc.push_back('0'+((B[0]&i)>0));
for(int i=0;i+1<B.size();i++)
getcycle(B[i]);
int dod=N-poc.size()-B.size()+2;
//cout<<"DOD JE "<<dod<<endl;
while(dod>0){
if(PQ.size()==0)
break;
// cout<<PQ.top().first<<" "<<PQ.top().second<<endl;
if(PQ.top().first<=dod){
// cout<<"UZEO "<<PQ.top().second<<endl;
dod-=PQ.top().first;
uzmi[PQ.top().second]=true;
PQ.pop();
}
else
PQ.pop();
}
if(dod!=0)
memset(uzmi,1,sizeof(uzmi));
for(int i=0;i+1<B.size();i++)
if(uzmi[B[i]])
poperm(B[i]);
else
R.push_back(B[i]);
}
else{
//cout<<"OVAKAV"<<endl;
for(int i=1;i<K;i++)
cout<<"0";
for(int i=1;i<V.size();i++)
cout<<(V[i]&1);
cout<<endl;
return 0;
}
// cout<<R.size()-1<<" "<<N-(K-1)<<endl;
string X=poc;
for(int i=0;i<N-poc.size();i++)
X.push_back('0'+(R[i]&1));
cout<<X<<"\n";
// cout<<count_substrings(X)<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 29672kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 6ms
memory: 28220kb
input:
5
output:
01100
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 3ms
memory: 30072kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 3ms
memory: 29676kb
input:
3
output:
010
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 3ms
memory: 29364kb
input:
4
output:
1001
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 3ms
memory: 30872kb
input:
6
output:
001110
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 0ms
memory: 30292kb
input:
7
output:
0010110
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 32024kb
input:
8
output:
00101110
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 0ms
memory: 30396kb
input:
9
output:
001011100
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 0ms
memory: 29112kb
input:
10
output:
0011101000
result:
ok meet maximum 42
Test #11:
score: 0
Accepted
time: 0ms
memory: 31500kb
input:
11
output:
00011110100
result:
ok meet maximum 50
Test #12:
score: 0
Accepted
time: 3ms
memory: 31372kb
input:
12
output:
000111101000
result:
ok meet maximum 59
Test #13:
score: -100
Wrong Answer
time: 4ms
memory: 44528kb
input:
200000
output:
000000000000000001000000001111111110000000100000000011111111000000001000000011111111110000001000000000011111110000000001000000111111111110000010000000000011111100000000001000001111111111110000100000000000011111000000000001000011111111111110001000000000000011110000000000001000111111111111110010000000...
result:
wrong answer not meet maximum 19996962126 < 19996962278