Submission #257158

#	Time	Username	Problem	Language	Result	Execution time	Memory
257158		Kastanda	Hidden Sequence (info1cup18_hidden)	C++11	87 / 100	5 ms	384 KiB

hidden

// 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;
        }

        /*printf("%d ::\n", k);
        for (int i = 0; i <= k; i ++)
                printf("%d ", A[i]);
        printf("\n");*/

        MXlen = n / 2 + 3;

        // 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]) F[i] = 1;
        for (int __ = 1; __ <= n; __ ++)
        for (int i = 0; i <= k; i ++)
                if (A[i] && F[i] == 1)
                {
                        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 = k; j > i; j --)
                        {
                                if (A[j])
                                        S2.push_back(w);
                                else if (A[j - 1] && j - 1 > i)
                                        S2.push_back(!w);
                        }
                        reverse(S2.begin(), S2.end());
                        int ff = 0;
                        for (int j = i + 1; j <= k; j ++)
                                ff |= A[j];
                        if (!ff) S2 = {};

                        for (int h = 0, sm = SZ[h]; h > i; h --)
                        {
                                if (F[h]) break;
                                if (h - 1 > i)
                                {
                                        sm += SZ[h - 1];
                                        if (F[h - 1])
                                                break;
                                }
                                vector < int > Tmp(sm, !w);
                                for (int j = h - 1; j > i; j --)
                                {
                                        if (A[j])
                                                Tmp.push_back(w);
                                        else if (A[j - 1] && j - 1 > i)
                                                Tmp.push_back(!w);
                                }
                                reverse(Tmp.begin(), Tmp.end());
                                if (Tmp.size() < S2.size())
                                        S2.swap(Tmp);
                        }

                        /*printf("%d =======================\n", i);
                        printf("%d :: ", i);
                        for (int a : S)
                                printf("%d ", a);
                        printf(":::: ");
                        for (int a : S2)
                                printf("%d ", a);
                        printf("\n");*/

                        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;
                        else
                                F[i] = 0;

                        //printf("%d :: %d :: %d\n", SZ[i], (int)Fail, F[i]);
                }
        /*for (int i = 0; i <= k; i ++)
                printf("(%d %d) ", SZ[i], F[i]);
        printf("\n");*/
        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 (stderr)

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: 15 / 20
• Subtask 2: 72 / 80