Submission #1100849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100849		Kirill22	Hidden Sequence (info1cup18_hidden)	C++17	87 / 100	6 ms	592 KiB

hidden

#include "bits/stdc++.h"

using namespace std;

bool isSubsequence (vector < int > v);

vector<int> findSequence(int N) {
    mt19937 gen(22);
    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;
    int O = cnt[1 - t];
    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;
        vector<int> ord(cnt[t] + 1);
        std::iota(ord.begin(), ord.end(), 0);
        std::shuffle(ord.begin(), ord.end(), gen);
        for (auto i : ord) {
            if (!O) {
//                break;
            }
            if (lens[i] == j - 1) {
                if (j == 1) {
                    vector<int> qu(i, t);
                    for (int k = 0; k < j; k++) {
                        qu.push_back(1 - t);
                    }
                    for (int k = 0; k < cnt[t] - i; k++) {
                        qu.push_back(t);
                    }
                    if (isSubsequence(qu)) {
                        lens[i] = j;
                        good++;
                        O--;
                    }
                } else {
                    vector<int> qu, qu2;
                    int cur = 0;
                    while (cur < i) {
                        if (lens[cur] > 0) {
                            qu.push_back(t);
                            cur++;
                        } else {
                            while (cur < i && lens[cur] == 0) {
                                cur++;
                            }
                            if (cur < i) {
                                qu.push_back(1 - t);
                            }
                        }
                    }
                    for (int k = 0; k < j; k++) {
                        qu.push_back(1 - t);
                    }
                    cur = cnt[t];
                    while (cur > i) {
                        if (lens[cur] > 0) {
                            qu2.push_back(t);
                            cur--;
                        } else {
                            while (cur > i && lens[cur] == 0) {
                                cur--;
                            }
                            if (cur > i) {
                                qu2.push_back(1 - t);
                            }
                        }
                    }
                    while (!qu2.empty()) {
                        qu.push_back(qu2.back());
                        qu2.pop_back();
                    }
                    if (isSubsequence(qu)) {
                        lens[i] = j;
                        good++;
                        O--;
                    }
                }
            }
        }
        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:23:20: warning: value computed is not used [-Wunused-value]
   23 |         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: 72 / 80