oj.uz

Submission #689879

# Submission time Handle Problem Language Result Execution time Memory
689879 2023-01-29T15:45:47 Z alexdd Hidden Sequence (info1cup18_hidden) C++17
59 / 100
 65 ms 312 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
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
        {
            ///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

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 = 7
3 Partially correct 1 ms 208 KB Output is partially correct: Maximum length of a query = 7
4 Correct 0 ms 208 KB Output is correct: Maximum length of a query = 5
5 Partially correct 0 ms 208 KB Output is partially correct: Maximum length of a query = 6

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 284 KB Output is partially correct: Maximum length of a query = 85
2 Correct 14 ms 208 KB Output is correct: Maximum length of a query = 90
3 Partially correct 50 ms 292 KB Output is partially correct: Maximum length of a query = 99
4 Partially correct 23 ms 300 KB Output is partially correct: Maximum length of a query = 83
5 Partially correct 46 ms 208 KB Output is partially correct: Maximum length of a query = 99
6 Partially correct 18 ms 312 KB Output is partially correct: Maximum length of a query = 100
7 Partially correct 24 ms 208 KB Output is partially correct: Maximum length of a query = 135
8 Partially correct 19 ms 300 KB Output is partially correct: Maximum length of a query = 95
9 Partially correct 14 ms 208 KB Output is partially correct: Maximum length of a query = 108
10 Partially correct 56 ms 208 KB Output is partially correct: Maximum length of a query = 103
11 Correct 65 ms 280 KB Output is correct: Maximum length of a query = 96
12 Partially correct 4 ms 304 KB Output is partially correct: Maximum length of a query = 149
13 Partially correct 50 ms 308 KB Output is partially correct: Maximum length of a query = 106