oj.uz

Submission #689869

# Submission time Handle Problem Language Result Execution time Memory
689869 2023-01-29T15:24:45 Z alexdd Hidden Sequence (info1cup18_hidden) C++17
54 / 100
 64 ms 304 KB 
#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

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;
    for(int i=totx;i>0;i--)
    {
        ///calc suff[i]
        if(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);
            suff[i]=0;
            for(int j=1;j<=toty;j++)
            {
                aux.insert(aux.begin()+i,y);
                if(!isSubsequence(aux))
                    break;
                suff[i]=j;
            }
            suff[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(!isSubsequence(aux))
                    break;
                suff[i]=j;
            }
        }
    }
    suff[0] = toty;
    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;
    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

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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 208 KB Output is partially correct: Maximum length of a query = 6
2 Partially correct 0 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 1 ms 208 KB Output is partially correct: Maximum length of a query = 9
5 Partially correct 1 ms 208 KB Output is partially correct: Maximum length of a query = 5

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 25 ms 280 KB Output is partially correct: Maximum length of a query = 85
2 Correct 11 ms 284 KB Output is correct: Maximum length of a query = 90
3 Partially correct 46 ms 208 KB Output is partially correct: Maximum length of a query = 99
4 Partially correct 22 ms 284 KB Output is partially correct: Maximum length of a query = 83
5 Partially correct 47 ms 208 KB Output is partially correct: Maximum length of a query = 99
6 Partially correct 19 ms 304 KB Output is partially correct: Maximum length of a query = 100
7 Partially correct 21 ms 208 KB Output is partially correct: Maximum length of a query = 135
8 Partially correct 19 ms 304 KB Output is partially correct: Maximum length of a query = 95
9 Partially correct 11 ms 284 KB Output is partially correct: Maximum length of a query = 108
10 Partially correct 57 ms 300 KB Output is partially correct: Maximum length of a query = 103
11 Correct 64 ms 284 KB Output is correct: Maximum length of a query = 96
12 Partially correct 4 ms 208 KB Output is partially correct: Maximum length of a query = 149
13 Partially correct 30 ms 300 KB Output is partially correct: Maximum length of a query = 106