oj.uz

Submission #257102

# Submission time Handle Problem Language Result Execution time Memory
257102 2020-08-03T15:33:33 Z Kastanda Hidden Sequence (info1cup18_hidden) C++11
0 / 100
 16 ms 256 KB 
// M
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;

vector < int > findSequence(int n)
{
        // Figuring out the lesser of the two
        int w;
        int MXlen = n / 2 + 1;
        vector < int > S(MXlen, 0);
        if (isSubsequence(S))
                w = 1;
        else
                w = 0;

        // Now to find the number of ws
        int k = n / 2;
        while (k && !isSubsequence(vector < int > (k, w)))
                k --;
        if (!k)
                return vector < int > (n, !w);

        // Next up, identifying non-empty sections
        vector < int > A(k + 1, 0);
        for (int i = 0; i <= k; i ++)
        {
                S = vector < int > (k + 1, w);
                S[i] = !w;
                if (isSubsequence(S))
                        A[i] = 1;
        }

        // Now to find the size of smaller sections
        vector < int > SZ(k + 1, 0);
        vector < int > F(k + 1, 0);
        for (int i = 0; i <= k; i ++)
                if (A[i])
                {
                        S = {};
                        for (int j = 0; j < i; j ++)
                        {
                                if (A[j])
                                        S.push_back(w);
                                else if (A[j + 1])
                                        S.push_back(!w);
                        }
                        if (S.size() && S.back() == !w)
                                S.pop_back();
                        vector < int > S2;
                        for (int j = i; j < k; j ++)
                        {
                                if (A[j])
                                        S2.push_back(w);
                                else if (A[j + 1])
                                        S2.push_back(!w);
                        }
                        if (S2.size() == 1)
                                S2 = {};
                        int sz = 1;
                        bool Fail = 0;
                        while ((int)S.size() + (int)S2.size() + sz + 1 <= MXlen)
                        {
                                sz ++;
                                vector < int > T = S;
                                for (int j = 0; j < sz; j ++)
                                        T.push_back(!w);
                                for (int a : S2)
                                        T.push_back(a);
                                if (!isSubsequence(T))
                                        {Fail = 1; sz --; break;}
                        }
                        SZ[i] = sz;
                        if (!Fail)
                                F[i] = 1;
                }
        int SM = k, cc = 0;
        for (int i = 0; i <= k; i ++)
                if (!F[i])
                        SM += SZ[i];
                else
                        cc ++;
        if (cc <= 1)
                for (int i = 0; i <= k; i ++)
                        if (F[i])
                                SZ[i] = n - SM;

        vector < int > Res;
        for (int i = 0; i <= k; i ++)
        {
                for (int j = 0; j < SZ[i]; j ++)
                        Res.push_back(!w);
                if (i < k)
                        Res.push_back(w);
        }
        return Res;

}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 5
2 Incorrect 0 ms 256 KB Output is not correct: The length of the returned sequence is not N
3 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 256 KB Output is not correct: The length of the returned sequence is not N
2 Halted 0 ms 0 KB -