Submission #1126195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126195		Captain_Georgia	Hidden Sequence (info1cup18_hidden)	C++20	34 / 100	348 ms	428 KiB

hidden

#include<bits/stdc++.h>
#include "grader.h"

using namespace std;

vector<int> findSequence (int N) {
    int x = N / 2 + 1, typ = 0;
    int low = 0, high = x;
    vector<int> tmp;
    while (low < high) {
        int mid = (low + high + 1) / 2;

        tmp.clear();
        for (int i = 0;i < mid;i ++) tmp.push_back(typ);

        if (isSubsequence (tmp) == true) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (low == x) {
        typ = 1;
        low = 0;
        high = x;
        while (low < high) {
            int mid = (low + high + 1) / 2;

            tmp.clear();
            for (int i = 0;i < mid;i ++) tmp.push_back(typ);

            if (isSubsequence (tmp) == true) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        assert(low < x);
    }

    vector<int> dre;
    int cnt_zero = low;
    N -= low;
    for (int i = 0;i <= cnt_zero;i ++) {
        low = 0;
        high = min(N + 1, x);
        while (low < high) {
            int mid = (low + high + 1) / 2;

            bool as = true;
            tmp.clear();
            for (int j = 0;j < i;j ++) {
                tmp.push_back(typ);
                if (isSubsequence (tmp) == false) {
                    as = false;
                    break;
                }
            }
            if (as == false) {
                high = mid - 1;
                continue;
            }
            for (int j = 0;j < mid;j ++) {
                tmp.push_back(1 - typ);
                if (isSubsequence (tmp) == false) {
                    as = false;
                    break;
                }
            }
            if (as == false) {
                high = mid - 1;
                continue;
            }
            for (int j = i;j < cnt_zero;j ++) {
                tmp.push_back(typ);
                if (isSubsequence (tmp) == false) {
                    as = false;
                    break;
                }
            }
            if (as == false) {
                high = mid - 1;
                continue;
            }

            if (isSubsequence (tmp) == true) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        if (low == x) {
            dre.push_back(-1);
        } else {
            dre.push_back (low);
            N -= low;
        }
    }
    for (auto &v : dre) if (v == -1) {
        v = N;
    }

    vector<int> answer;
    for (int i = 0;i < dre.size();i ++) {
        // cout << dre[i] << " ";
        for (int j = 0;j < dre[i];j ++) answer.push_back(1 - typ);
        if (i + 1 < dre.size()) answer.push_back(typ);
    }
    return answer;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 20
• Subtask 2: 24 / 80