Submission #401324

#	Time	Username	Problem	Language	Result	Execution time	Memory
401324		Victor	Hidden Sequence (info1cup18_hidden)	C++17	0 / 100	7 ms	328 KiB

hidden

#include <bits/stdc++.h>

#include "grader.h"

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vector<int> findSequence(int n) {
    vector<int> ans(n, -1);
    vi subseq;

    int left[2], taken[2];
    taken[0] = taken[1] = 0;

    int zeros, ones, len = n / 2 + 1, small = 0, big = 1;
    zeros = -1;

    rep(i, 1, len + 1) {
        subseq.pb(0);
        if (!isSubsequence(subseq)) {
            zeros = i - 1;
            break;
        }
    }

    if (zeros == -1) {
        subseq.clear();
        rep(i, 1, len + 1) {
            subseq.pb(1);
            if (!isSubsequence(subseq)) {
                ones = i - 1;
                break;
            }
        }
        zeros = n - ones;
        swap(small, big);

    } else
        ones = n - zeros;

    left[0] = zeros;
    left[1] = ones;
    subseq.clear();

    rep(k, 0, 2) {
        left[0] = zeros;
        left[1] = ones;
        subseq.clear();

        per(i, (n + 1) / 2, n) {
            vi query = subseq;
            int add;
            query.insert(query.begin(), big);
            rep(j, 0, left[small]) query.insert(query.begin(), small);

            if (k) reverse(all(query));
            if (sz(query) <= len) {
                if (isSubsequence(query))
                    add = big;
                else
                    add = small;

            } else {
                query.clear();

                rep(j, 0, left[big]) query.pb(big);
                rep(j, 0, taken[small] + 1) query.pb(small);
                if (k) reverse(all(query));
                if (isSubsequence(query))
                    add = small;
                else
                    add = big;
            }

            --left[add];
            ++taken[add];
            subseq.insert(subseq.begin(), add);
            ans[k ? n - i - 1 : i] = add;
        }
    }

    if (n & 2) {
        rep(i, 0, n) if (ans[i] == 0)-- zeros;
        if (zeros)
            ans[n >> 1] = 0;
        else
            ans[n >> 1] = 1;
    }

    return ans;
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:76:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |             if (sz(query) <= len) {
      |                           ^
hidden.cpp:54:15: warning: 'ones' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         zeros = n - ones;
      |         ~~~~~~^~~~~~~~~~
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: 0 / 20
• Subtask 2: 0 / 80