| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1320818 | hoangmc2009 | Hidden Sequence (info1cup18_hidden) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#ifndef Graven
#include "grader.h"
#endif
#ifdef Graven
int maxQ=0;
vector<int> F;
bool isSubSeq(const vector<int>& v)
{
if (v.size()>maxQ) maxQ=v.size();
for(int i=0,j=0;i<v.size();++i)
{
while(j<F.size() and v[i]!=F[j]) ++j;
if(j==F.size()) return false;
else ++j;
}
return true;
}
#endif
vector<int> findSequence (int N)
{
if(N<=4)
{
for(int i=0;i<(1<<N);++i)
{
vector<int> wh;
for(int j=0;j<N;++j) wh.push_back((i>>j)&1);
if(isSubSeq(wh)) return wh;
}
}
else
{
vector<int> tmp(N,1),res;
while(!isSubSeq(tmp)) tmp.pop_back();
for(int i=tmp.size(),c0=0;i>=0;--i)
{
while(tmp.size()<N) tmp.push_back(0);
while(!isSubSeq(tmp)) tmp.pop_back();
for(int j=0;j<c0;++j) tmp.pop_back();
while(!tmp.empty() and tmp.back()==0)
{
res.push_back(0);
tmp.pop_back(); ++c0;
}
if(i>0)
{
res.push_back(1);
tmp.pop_back();
}
}
reverse(res.begin(),res.end());
return res;
}
}
#ifdef Graven
int main()
{
int n, x;
scanf ("%d", &n), maxQ = 0;
for (int i=1; i<=n; i++)
scanf ("%d", &x), F.push_back(x);
vector<int> ans=findSequence(n);
if (ans.size () != F.size ())
{
printf ("Different lengths\n");
for (auto it : ans) printf ("%d ", it);
printf ("\n");
return 0;
}
for (int i=0;i<ans.size();i++)
{
if (ans[i]!=F[i])
{
printf("WA position %d\n",i+1);
for (auto it : ans) printf ("%d ", it);
printf ("\n");
return 0;
}
}
printf ("Ok, biggest queried length %d\n", maxQ);
return 0;
}
#endif