Submission #197371

#	Time	Username	Problem	Language	Result	Execution time	Memory
197371		Nicksechko	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	13 ms	380 KiB

hidden

#include "grader.h"
#include <vector>
#include <algorithm>

using namespace std;

vector<int> findSequence(int n) {
    const int max_query_cnt = n / 2 + 1;

    int leq = 0;
    int geq = 1;

    vector<int> sequence;

    while (sequence.size() < max_query_cnt && isSubsequence(sequence)) {
        sequence.push_back(geq);
    }

    if (!isSubsequence(sequence)) {
        swap(leq, geq);
    } else {
        sequence.clear();
        while (sequence.size() <= max_query_cnt && isSubsequence(sequence)) {
            sequence.push_back(leq);
        }
    }

    sequence.pop_back();

    int cnt = sequence.size();

    vector<int> pref(cnt), suff(cnt);
    vector<int> pref_sequence = sequence;
    vector<int> suff_sequence = sequence;

    for (int i = 0; i < cnt; i++) {
        while (pref_sequence.size() <= max_query_cnt && isSubsequence(pref_sequence)) {
            pref_sequence.insert(pref_sequence.begin(), geq);
        }
        while (suff_sequence.size() <= max_query_cnt && isSubsequence(suff_sequence)) {
            suff_sequence.push_back(geq);
        }

        pref[i] = pref_sequence.size() + i - cnt - 1;
        suff[i] = suff_sequence.size() - 1;

        pref_sequence.pop_back();
        suff_sequence.erase(suff_sequence.begin());
    }

    reverse(suff.begin(), suff.end());

    sequence.clear();
    for (int i = 0; i < cnt; i++) {
        if (suff[i] != n / 2 + 1) {
            pref[i] = n - cnt - suff[i] + i + 1;
        }
        fill_n(back_inserter(sequence), pref[i] - (i == 0 ? 0 : pref[i  - 1]), geq);
        sequence.push_back(leq);
    }

    fill_n(back_inserter(sequence), n - sequence.size(), geq);

    return sequence;
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:15:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (sequence.size() < max_query_cnt && isSubsequence(sequence)) {
            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
hidden.cpp:23:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (sequence.size() <= max_query_cnt && isSubsequence(sequence)) {
                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
hidden.cpp:37:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pref_sequence.size() <= max_query_cnt && isSubsequence(pref_sequence)) {
                ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
hidden.cpp:40:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (suff_sequence.size() <= max_query_cnt && isSubsequence(suff_sequence)) {
                ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
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: 20 / 20
• Subtask 2: 80 / 80