# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
974196 | emptypringlescan | Hidden Sequence (info1cup18_hidden) | C++17 | 610 ms | 440 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>
using namespace std;
#include "grader.h"
vector<int> findSequence(int n){
int use=0;
vector<int> tst;
for(int i=0; i<n/2+1; i++) tst.push_back(0);
if(isSubsequence(tst)) use=1;
int len=n/2;
for(; len>=0; len--){
tst.clear();
for(int j=0; j<len; j++) tst.push_back(use);
if(isSubsequence(tst)) break;
} //len of use
//cout << len << ' ' << use << '\n';
int oth[len+1];
memset(oth,-1,sizeof(oth));
bool can=false;
int yay=n/2+2;
for(int j=0; j<=len; j++){
int num=yay-len;
for(; num>=0; num--){
tst.clear();
for(int i=0; i<j; i++) tst.push_back(use);
for(int i=0; i<num; i++) tst.push_back(!use);
for(int i=j; i<len; i++) tst.push_back(use);
if(isSubsequence(tst)) break;
}
if(num<yay-len){
can=true;
oth[j]=num;
}
}
for(int i=len-1; i>=0; i--){
for(int j=0; j<=i; j++){
int num=yay-i;
for(; num>=0; num--){
tst.clear();
for(int x=0; x<j; x++) tst.push_back(use);
for(int x=0; x<num; x++) tst.push_back(!use);
for(int x=j; x<i; x++) tst.push_back(use);
if(isSubsequence(tst)) break;
}
if(num<yay-i){
bool ok=true;
int unk=-1,sm=0;
for(int k=j; k<=j+len-i; k++){
if(oth[k]==-1){
if(unk!=-1) ok=false;
else unk=k;
}
else sm+=oth[k];
}
if(ok&&unk!=-1){
oth[unk]=num-sm;
}
}
}
}
bool ok=true;
int unk=-1,sm=0;
for(int i=0; i<=len; i++){
if(oth[i]==-1){
if(unk!=-1) ok=false;
else unk=i;
}
else sm+=oth[i];
}
if(!ok){
int rep=(n-sm-len)/2;
for(int i=0; i<=len; i++) if(oth[i]==-1) oth[i]=rep;
}
else if(unk!=-1) oth[unk]=n-sm-len;
vector<int> ret;
for(int i=0; i<=len; i++){
for(int j=0; j<oth[i]; j++) ret.push_back(!use);
ret.push_back(use);
}
ret.pop_back();
return ret;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |