Submission #401608

#	Time	Username	Problem	Language	Result	Execution time	Memory
401608		Victor	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	8 ms	332 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;

    rep(k, 0, 2) {
        left[0] = zeros;
        left[1] = ones;
        taken[0] = taken[1] = 0;
        subseq.clear();
        int val = k ? 1 : -1, start = k ? 0 : n - 1;

        for (int i = start; 0 <= i && i < n; i += val) {
            if (ans[i] != -1) break;

            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 (sz(query) <= len) {
                    if (k) reverse(all(query));
                    if (isSubsequence(query))
                        add = small;
                    else
                        add = big;

                } else {
                    query.clear();
                    rep(j, 0, left[small]) query.pb(small);
                    rep(j, 0, taken[big] + 1) query.pb(big);

                    if (len < sz(query)) break;
                    if (k) reverse(all(query));

                    if (isSubsequence(query))
                        add = big;
                    else
                        add = small;
                }
            }

            --left[add];
            ++taken[add];
            subseq.insert(subseq.begin(), add);
            ans[i] = add;
        }
    }

    int pos = -1;
    rep(i, 0, n) {
        if (ans[i] == 1) --ones;
        if (!ans[i]) --zeros;
    }

    //cout << ones << ' ' << zeros << endl;
    //rep(i, 0, n) cout << ans[i] << ' ';
    //cout << endl;

    if (zeros) rep(i, 0, n) if (ans[i] == -1) ans[i] = 0;
    if (ones) rep(i, 0, n) if (ans[i] == -1) ans[i] = 1;

    return ans;
}


/*
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 = 7, x;
    theRealAnswer.resize(n);
    rep(i, 0, 1<<n) {
        maxQ = 0;
        rep(j, 0, n) theRealAnswer[j] = (i & (1 << j)) ? 1 : 0;
        //rep(j, 0, n) cout << theRealAnswer[j] << ' ';
        //cout << endl<<endl;

        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 j = 0; j < ans.size(); j++)
            if (ans[j] != theRealAnswer[j]) {
                printf("WA position %d\n", j + 1);
                for (auto it : ans)
                    printf("%d ", it);
                printf("\n");
                cout<<i<<endl;
                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: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:87:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |                 if (sz(query) <= len) {
      |                               ^
hidden.cpp:99:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                     if (len < sz(query)) break;
      |                             ^
hidden.cpp:116:9: warning: unused variable 'pos' [-Wunused-variable]
  116 |     int pos = -1;
      |         ^~~
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: 20 / 20
• Subtask 2: 80 / 80