# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
923398 | vjudge1 | Hidden Sequence (info1cup18_hidden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "grader.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
#define pb push_back
vector<int> findSequence(int n){
int L=(n/2)+1;
int c1=-1,c0=-1;
for(int i=1;i<=L;i++){
vector<int> v;
for(int j=1;j<=i;j++)v.pb(1);
if(!isSubsequence(v)){
c1=i-1;
c0=n-c1;
break;
}
}
for(int i=1;i<=L;i++){
vector<int> v;
for(int j=1;j<=i;j++)v.pb(0);
if(!isSubsequence(v)){
c0=i-1;
c1=n-c0;
break;
}
}
if(c1<=0){
for(int i=1;i<=n;i++)ans.pb(0);
return ans;
}
if(c0<=0){
for(int i=1;i<=n;i++)ans.pb(1);
return ans;
}
vector<int> ans;
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++){
if(!c1){
ans.pb(0);
continue;
}
if(!c0){
ans.pb(1);
continue;
}
vector<int> v;
if(cnt0<=cnt1){
for(int i=1;i<=cnt0;i++)v.pb(0);
}
else{
for(int i=1;i<=cnt1;i++)v.pb(1);
}
if(!ans.empty()){
if(v.empty())v.pb(ans.back());
else if(v.back()!=ans.back())ans.pb(ans.back());
}
if(c0<=c1){
v.pb(1);
for(int i=1;i<=c0;i++)v.pb(0);
if(!isSubsequence(v)){
ans.pb(0);
c0--;
cnt0++;
}
else{
ans.pb(1);
c1--;
cnt1++;
}
}
else{
ans.pb(0);
for(int i=1;i<=c1;i++)ans.pb(1);
if(isSubsequence(v)){
ans.pb(0);
c0--;
cnt0++;
}
else{
ans.pb(1);
c1--;
cnt1++;
}
}
}
assert(c0+c1==0);
return ans;
}