Submission #1100840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100840		Kirill22	Hidden Sequence (info1cup18_hidden)	C++17	59 / 100	7 ms	712 KiB

hidden

#include "bits/stdc++.h"

using namespace std;

bool isSubsequence (vector < int > v);

vector<int> findSequence(int N) {
    int mx = N / 2 + 1;
    vector<int> cnt(2);
    for (int t = 0; t < 2; t++) {
        for (int i = 1; i <= mx; i++) {
            vector<int> qu(i, t);
            if (isSubsequence(qu)) {
                cnt[t] = i;
            } else {
                break;
            }
        }
    }
    int t = 0;
    if (cnt[0] > cnt[1]) {
        cnt[0] - N - cnt[1];
        t = 1;
    } else {
        cnt[1] = N - cnt[0];
        t = 0;
    }
    vector<int> lens(cnt[t] + 1), pref;
    for (int j = 1; j <= mx; j++) {
        int good = 0;
        pref.resize(lens.size() + 1);
        for (int i = 1; i < (int) pref.size(); i++) {
            pref[i] = pref[i - 1] + int(lens[i - 1] != 0 || j == 1);
        }
//        for (auto& x : pref) cout << x << " + " ; cout << endl;
        for (int i = 0; i <= cnt[t]; i++) {
            if (lens[i] == j - 1) {
                bool chk = false;
                for (int s = 0; s <= cnt[t] && !chk; s++) {
                    for (int l = 0; l <= i && !chk; l++) {
                        int r = s - l;
                        if (r > cnt[t] - i || r < 0) continue;
                        int L = l, R = cnt[t] - r;
//                        cout << i << " " << l << " " << r << endl;
                        if (pref[R + 1] - pref[L] == 1) {
//                            cout << j << " " << i << " " << l << " " << r << endl;
                            chk = true;
                            vector<int> qu(l, t);
                            for (int k = 0; k < j; k++) {
                                qu.push_back(1 - t);
                            }
                            for (int k = 0; k < r; k++) {
                                qu.push_back(t);
                            }
                            if (isSubsequence(qu)) {
                                lens[i] = j;
                                good++;
                            }
                        }
                    }
                }
            }
        }
        if (good <= 1) {
            break;
        }
    }
    int pos = std::max_element(lens.begin(), lens.end()) - lens.begin();
    int S = std::accumulate(lens.begin(), lens.end(), 0);
    lens[pos] = N - (cnt[t] + (S - lens[pos]));
    vector<int> answer(lens[0], 1 - t);
    for (int i = 1; i <= cnt[t]; i++) {
        answer.push_back(t);
        for (int j = 0; j < lens[i]; j++) {
            answer.push_back(1 - t);
        }
    }
    return answer;
}

//static int maxQ = 0;
//static vector < int > theRealAnswer;
//
//bool isSubsequence (vector < int > v)
//{
//    if (v.size () > maxQ)
//        maxQ = v.size ();
//    int i = 0;
//    for (auto it : v)
//    {
//        while (i < theRealAnswer.size () && it != theRealAnswer[i]) i ++;
//        if (i == theRealAnswer.size ()) return 0;
//        i ++;
//    }
//    return 1;
//}
//
//int main ()
//{
//    int n, x;
//    scanf ("%d", &n), maxQ = 0;
//    for (int i=1; i<=n; i++)
//        scanf ("%d", &x), theRealAnswer.push_back (x);
//
//    vector < int > ans = findSequence (n);
//    if (ans.size () != theRealAnswer.size ())
//    {
//        printf ("Different lengths\n");
//        for (auto it : ans)
//            printf ("%d ", it);
//        printf ("\n");
//        return 0;
//    }
//
//    for (int i=0; i<ans.size (); i++)
//        if (ans[i] != theRealAnswer[i])
//        {
//            printf ("WA position %d\n", i + 1);
//            for (auto it : ans)
//                printf ("%d ", it);
//            printf ("\n");
//            return 0;
//        }
//    printf ("Ok, biggest queried length %d\n", maxQ);
//    return 0;
//}
//

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:22:20: warning: value computed is not used [-Wunused-value]
   22 |         cnt[0] - N - cnt[1];
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 / 20
• Subtask 2: 44 / 80