Submission #494801

#	Time	Username	Problem	Language	Result	Execution time	Memory
494801		syl123456	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	9 ms	340 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 + 1;
    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;
    bool rev = false;
    if (zro > one)
        swap(zro, one), rev = true;
    auto gen = [&](int pos, int cnt) {
        vector<int> res(pos, 0);
        res.insert(res.end(), cnt, 1);
        res.insert(res.end(), zro - pos, 0);
        if (rev)
            for (int &i : res)
                i = !i;
        return res;
    };
    int a[zro + 1]{}, rem = zro + 1;
    bool ok[zro + 1]{};
    for (int i = 0; i < zro + 1; ++i) {
        for (int j = 1; zro + j <= mx; ++j)
            if (isSubsequence(gen(i, j)))
                ++a[i], --one;
            else {
                ok[i] = true;
                --rem;
                break;
            }
    }
    auto gen2 = [&](int pos, int cnt) {
        vector<int> res;
        int nxt = -1;
        for (int i = 0; i < pos; ++i) {
            if (a[i]) {
                if (nxt == -1)
                    res.push_back(0);
                else {
                    res.push_back(1);
                    if (a[i] > 1 || !ok[i])
                        res.push_back(0), nxt = -1;
                    else
                        nxt = 0;
                }
            }
            else {
                if (nxt == -1)
                    nxt = 0;
            }
        }
        res.insert(res.end(), cnt, 1);
        vector<int> suf;
        nxt = -1;
        for (int i = zro - 1; i >= pos; --i) {
            if (a[i + 1]) {
                if (nxt == -1)
                    suf.push_back(0);
                else {
                    suf.push_back(1);
                    if (a[i + 1] > 1 || !ok[i + 1])
                        suf.push_back(0), nxt = -1;
                    else
                        nxt = 0;
                }
            }
            else {
                if (nxt == -1)
                    nxt = 0;
            }
        }
        res.insert(res.end(), suf.rbegin(), suf.rend());
        if (rev)
            for (int &i : res)
                i = !i;
        return 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 = gen2(i, a[i] + 1);
                while (tmp.size() <= mx) {
                    upd = true;
                    if (isSubsequence(tmp))
                        ++a[i], --one;
                    else {
                        ok[i] = true;
                        --rem;
                        break;
                    }
                    tmp = gen2(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();
    if (rev)
        for (int &i : ans)
            i = !i;
    return ans;
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:135:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |                 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: 20 / 20
• Subtask 2: 80 / 80