Submission #494793

#	Time	Username	Problem	Language	Result	Execution time	Memory
494793		syl123456	Hidden Sequence (info1cup18_hidden)	C++17	0 / 100	13 ms	544 KiB

hidden

#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#include "grader.h"
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

vector<int> findSequence(int n) {
    int mx = n / 2 + 3;
    int zro = -1;
    for (int i = 1; i <= mx; ++i)
        if (!isSubsequence(vector<int>(i, 0))) {
            zro = i - 1;
            break;
        }
    if (zro == -1) {
        for (int i = 1; i <= mx; ++i)
            if (!isSubsequence(vector<int>(i, 1))) {
                zro = n - i + 1;
                break;
            }
    }
    int one = n - zro;
    if (zro <= one) {
        int a[zro + 1]{}, rem = zro + 1;
        bool ok[zro + 1]{};
        auto gen = [&](int pos, int cnt) {
            deque<int> res(cnt, 1);
            int last = 1;
            for (int i = pos - 1; ~i; --i) {
                if (last == 0) {
                    if (a[i] > 1 || !ok[i])
                        res.push_front(1), last = 1;
                    else if (a[i] == 1)
                        res.push_front(1);
                }
                else {
                    res.push_front(0);
                    if (!a[i] && ok[i])
                        last = 0;
                }
            }
            last = 1;
            for (int i = pos; i < zro; ++i) {
                if (last == 0) {
                    if (a[i + 1] > 1 || !ok[i])
                        res.push_back(1), last = 1;
                    else if (a[i + 1] == 1)
                        res.push_back(1);
                }
                else {
                    res.push_back(0);
                    if (!a[i + 1] && ok[i])
                        last = 0;
                }
            }
            return vector<int>(all(res));
        };
        while (rem > 1 && one) {
            bool upd = false;
            for (int i = 0; i < zro + 1 && rem > 1 && one; ++i)
                if (!ok[i]) {
                    vector<int> tmp = gen(i, a[i] + 1);
                    while (tmp.size() <= mx) {
                        upd = true;
                        if (isSubsequence(tmp))
                            ++a[i], --one;
                        else {
                            ok[i] = true;
                            --rem;
                            break;
                        }
                        tmp = gen(i, a[i] + 1);
                    }
                }
            if (!upd)
                break;
        }
        for (int i = 0; i < zro + 1; ++i)
            if (!ok[i])
                a[i] += one, one = 0;
        vector<int> ans;
        for (int i = 0; i < zro + 1; ++i)
            ans.insert(ans.end(), a[i], 1), ans.push_back(0);
        ans.pop_back();
        return ans;
    }
    else {
        swap(zro, one);
        int a[zro + 1]{}, rem = zro + 1;
        bool ok[zro + 1]{};
        auto gen = [&](int pos, int cnt) {
            deque<int> res(cnt, 1);
            int last = 1;
            for (int i = pos - 1; ~i; --i) {
                if (last == 0) {
                    if (a[i] > 1 || !ok[i])
                        res.push_front(1), last = 1;
                    else if (a[i] == 1)
                        res.push_front(1);
                }
                else {
                    res.push_front(0);
                    if (!a[i] && ok[i])
                        last = 0;
                }
            }
            last = 1;
            for (int i = pos; i < zro; ++i) {
                if (last == 0) {
                    if (a[i + 1] > 1 || !ok[i])
                        res.push_back(1), last = 1;
                    else if (a[i + 1] == 1)
                        res.push_back(1);
                }
                else {
                    res.push_back(0);
                    if (!a[i + 1] && ok[i])
                        last = 0;
                }
            }
            for (int &i : res)
                i = !i;
            return vector<int>(all(res));
        };
        while (rem > 1 && one) {
            bool upd = false;
            for (int i = 0; i < zro + 1 && rem > 1 && one; ++i)
                if (!ok[i]) {
                    vector<int> tmp = gen(i, a[i] + 1);
                    while (tmp.size() <= mx) {
                        upd = true;
                        if (isSubsequence(tmp))
                            ++a[i], --one;
                        else {
                            ok[i] = true;
                            --rem;
                            break;
                        }
                        tmp = gen(i, a[i] + 1);
                    }
                }
            if (!upd)
                break;
        }
        for (int i = 0; i < zro + 1; ++i)
            if (!ok[i])
                a[i] += one, one = 0;
        vector<int> ans;
        for (int i = 0; i < zro + 1; ++i)
            ans.insert(ans.end(), a[i], 1), ans.push_back(0);
        ans.pop_back();
        for (int &i : ans)
            i = !i;
        return ans;
    }
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:100:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |                     while (tmp.size() <= mx) {
      |                            ~~~~~~~~~~~^~~~~
hidden.cpp:167:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  167 |                     while (tmp.size() <= mx) {
      |                            ~~~~~~~~~~~^~~~~
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