Submission #689873

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
689873	2023-01-29T15:37:59 Z	alexdd	Hidden Sequence (info1cup18_hidden)	C++17	15 / 100	59 ms	296 KB

hidden

#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(i+suff[i+1]>totx || bl)///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
        {
            ///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];
        suff[unde] = cate[unde] + suff[unde+1];
    }
    vector<int> sol;
    for(int i=0;i<=totx;i++)
    {
        for(int j=1;j<=suff[i]-suff[i+1];j++)
            sol.push_back(y);
        if(i<totx)
            sol.push_back(x);
    }
    return sol;
}

vector<int>findSequence(int N)
{
    n=N;
    limit = n/2 + 3;
    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

hidden.cpp: In function 'std::vector<int> solve(int, int)':
hidden.cpp:49:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |                 if(aux.size()>limit && !bl)
      |                    ~~~~~~~~~~^~~~~~
hidden.cpp:72:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |                 if(aux.size()>limit && !bl)
      |                    ~~~~~~~~~~^~~~~~
grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<ans.size () && i < N; i++)
      |                   ~^~~~~~~~~~~~

Subtask #1

15.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	208 KB	Output is partially correct: Maximum length of a query = 6
2	Partially correct	1 ms	208 KB	Output is partially correct: Maximum length of a query = 8
3	Partially correct	1 ms	208 KB	Output is partially correct: Maximum length of a query = 6
4	Partially correct	0 ms	208 KB	Output is partially correct: Maximum length of a query = 7
5	Partially correct	0 ms	208 KB	Output is partially correct: Maximum length of a query = 5

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	21 ms	288 KB	Output is partially correct: Maximum length of a query = 85
2	Correct	18 ms	296 KB	Output is correct: Maximum length of a query = 90
3	Incorrect	59 ms	208 KB	Output is not correct: The length of the returned sequence is not N
4	Halted	0 ms	0 KB	-