# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
689880 | alexdd | Hidden Sequence (info1cup18_hidden) | C++17 | 68 ms | 320 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"
using namespace std;
int n;
int totx,toty;
int suff[205];///suff[i] = cate y-uri exista dupa al i-lea x
int cate[205];
int limit;
vector<int> solve(int x, int y)///avem mai putine x-uri decat y-uri
{
vector<int> allx;
for(int i=1;i<=(n+1)/2;i++)
allx.push_back(x);
for(int i=(n+1)/2;i>=0;i--)
{
if(isSubsequence(allx))
{
totx=i;
toty=n-i;
break;
}
allx.pop_back();
}
if(totx==0)
{
allx.clear();
for(int i=1;i<=n;i++)
allx.push_back(y);
return allx;
}
vector<int> aux;
bool bl=0;
int unde;
for(int i=totx;i>=0;i--)
{
///calc suff[i]
if(bl || i+suff[i+1]>totx)///punem x-uri dupa
{
///folosim totx + cnty
aux.clear();
for(int j=1;j<=totx;j++)
aux.push_back(x);
cate[i]=0;
for(int j=1;j<=toty;j++)
{
aux.insert(aux.begin()+i,y);
if(aux.size()>limit && !bl)
{
cate[i]=-1;
bl=1;
unde=i;
break;
}
if(!isSubsequence(aux))
break;
cate[i]=j;
}
suff[i]=cate[i]+suff[i+1];
}
else///nu punem nimic dupa
{
if(i==0)
{
suff[i]=toty;
cate[i]=suff[i] - suff[i+1];
break;
}
///folosim i + cnty + suff[i+1]
aux.clear();
for(int j=1;j<=i;j++)
aux.push_back(x);
suff[i]=0;
for(int j=1;j<=toty;j++)
{
aux.push_back(y);
if(aux.size()>limit && !bl)
{
bl=1;
suff[i]=-1;
cate[i]=-1;
unde=i;
break;
}
if(!isSubsequence(aux))
break;
suff[i]=j;
}
cate[i] = suff[i]-suff[i+1];
}
}
if(bl)
{
int sum=0;
for(int i=0;i<unde;i++)
sum+=cate[i];
cate[unde] = toty - sum - suff[unde+1];
}
vector<int> sol;
for(int i=0;i<=totx;i++)
{
for(int j=1;j<=cate[i];j++)
sol.push_back(y);
if(i<totx)
sol.push_back(x);
}
return sol;
}
vector<int>findSequence(int N)
{
n=N;
if(n<=10)
limit = n/2 + 1;
else
limit = (3*n)/4 + 1;
vector<int> all0;
for(int i=1;i<=(n+1)/2;i++)
{
all0.push_back(0);
}
if(!isSubsequence(all0))
return solve(0,1);
else
return solve(1,0);
}
/**
presupunem ca exista mai putine 0-uri decat 1-uri
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |