| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317539 | 2020-10-30T01:51:55 Z | daniel920712 | Hidden Sequence (info1cup18_hidden) | C++14 | 7 ms | 384 KB |
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
vector < pair < vector < int > , int > > all;
vector < int > temp;
vector < int > tt;
vector < int > ans;
vector < int > ans2;
vector < int > ans3;
set < int > have;
vector < int > Not;
deque < int > fin;
int con[5005]={0};
vector < int > findSequence (int N)
{
int i,j,k,l,ok=0,now=0,x1=0,y1=0,x,y,ll,rr;
if(N<=10)
{
for(i=0;i<(1<<(N/2+1));i++)
{
temp.clear();
for(j=0;j<(N/2+1);j++)
{
if(i&(1<<j)) temp.push_back(1);
else temp.push_back(0);
}
all.push_back(make_pair(temp,isSubsequence(temp)));
}
for(i=0;i<(1<<N);i++)
{
temp.clear();
for(j=0;j<N;j++)
{
if(i&(1<<j)) temp.push_back(1);
else temp.push_back(0);
}
ok=1;
for(auto j:all)
{
now=0;
for(auto k:temp)
{
if(now<N/2+1&&k==j.first[now]) now++;
}
if(now==N/2+1&&j.second==0) ok=0;
if(now!=N/2+1&&j.second==1) ok=0;
}
if(ok) return temp;
}
temp.clear();
return temp;
}
else
{
for(i=0;i<N/2+1;i++)
{
temp.push_back(0);
if(!isSubsequence(temp))
{
x=i;
break;
}
}
temp.clear();
if(i==N/2+1)
{
for(i=0;i<N/2+1;i++)
{
temp.push_back(1);
if(!isSubsequence(temp))
{
x=N-i;
break;
}
}
}
y=N-x;
if(x<=N/2)
{
for(i=0;i<=x;i++) have.insert(i);
for(i=1;have.size()>1;i++)
{
//printf("aa %d %d\n",i,have.size());
Not.clear();
for(auto j:have)
{
temp.clear();
for(k=0;k<=x;k++)
{
ll=k;
rr=x-k;
if(j==k) for(l=0;l<i;l++) fin.push_back(1);
if(k!=x) fin.push_back(0);
}
while(fin.size()>N/2+3)
{
if(ll<=1)
{
fin.pop_back();
rr--;
}
else if(rr<=1)
{
fin.pop_front();
ll--;
}
else
{
ll--;
fin.pop_front();
}
}
while(!fin.empty())
{
temp.push_back(fin.front());
fin.pop_front();
}
if(!isSubsequence(temp))
{
//printf("bb %d\n",j);
con[j]=i-1;
y-=(i-1);
Not.push_back(j);
}
}
for(auto j:Not) have.erase(j);
}
if(!have.empty()) con[*have.begin()]=y;
for(i=0;i<=x;i++)
{
for(j=0;j<con[i];j++) ans.push_back(1);
if(i!=x) ans.push_back(0);
}
return ans;
}
else
{
for(i=0;i<=y;i++) have.insert(i);
for(i=1;have.size()>1;i++)
{
Not.clear();
for(auto j:have)
{
temp.clear();
for(k=0;k<=y;k++)
{
if(j==k) for(l=0;l<i;l++) temp.push_back(0);
if(k!=y) temp.push_back(1);
}
if(!isSubsequence(temp))
{
//printf("bb %d\n",j);
con[j]=i-1;
x-=(i-1);
Not.push_back(j);
}
}
for(auto j:Not) have.erase(j);
}
if(!have.empty()) con[*have.begin()]=x;
for(i=0;i<=y;i++)
{
for(j=0;j<con[i];j++) ans.push_back(0);
if(i!=y) ans.push_back(1);
}
return ans;
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 256 KB | Output is correct: Maximum length of a query = 5 |
| 2 | Correct | 3 ms | 288 KB | Output is correct: Maximum length of a query = 6 |
| 3 | Correct | 1 ms | 384 KB | Output is correct: Maximum length of a query = 5 |
| 4 | Correct | 2 ms | 384 KB | Output is correct: Maximum length of a query = 5 |
| 5 | Correct | 1 ms | 256 KB | Output is correct: Maximum length of a query = 4 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 4 ms | 376 KB | Output is partially correct: Maximum length of a query = 85 |
| 2 | Correct | 6 ms | 384 KB | Output is correct: Maximum length of a query = 90 |
| 3 | Incorrect | 7 ms | 376 KB | Output is not correct: The length of the returned sequence is not N |
| 4 | Halted | 0 ms | 0 KB | - |