Submission #494787

#	Time	Username	Problem	Language	Result	Execution time	Memory
494787		syl123456	Hidden Sequence (info1cup18_hidden)	C++17	15 / 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;
 
bool isSubsequence(vector<int> s);

 
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) {
        auto gen = [&](int pos, int cnt) {
            vector<int> res(pos, 0);
            res.insert(res.end(), cnt, 1);
            res.insert(res.end(), zro - pos, 0);
            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) {
            deque<int> res(cnt, 1);
            int last = 0;
            for (int i = pos - 1; ~i; --i) {
                if (last == 0) {
                    if (a[i] == 1)
                        res.push_front(1);
                    else if (a[i] > 1)
                        res.push_front(1), last = 1;
                }
                else {
                    res.push_front(0);
                    if (!a[i])
                        last = 0;
                }
            }
            last = 0;
            for (int i = pos; i < zro; ++i) {
                if (last == 0) {
                    if (a[i + 1] == 1)
                        res.push_back(1);
                    else if (a[i + 1] > 1)
                        res.push_back(1), last = 1;
                }
                else {
                    res.push_back(0);
                    if (!a[i + 1])
                        last = 0;
                }
            }
            return vector<int>(all(res));
        };
        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) {
                    if (isSubsequence(tmp))
                        ++a[i], --one;
                    else {
                        ok[i] = true;
                        --rem;
                        break;
                    }
                    tmp = gen2(i, a[i] + 1);
                }
            }
        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 {
        auto gen = [&](int pos, int cnt) {
            vector<int> res(pos, 1);
            res.insert(res.end(), cnt, 0);
            res.insert(res.end(), one - pos, 1);
            return res;
        };
        int a[one + 1]{}, rem = one + 1;
        bool ok[one + 1]{};
        for (int i = 0; i < one + 1; ++i) {
            for (int j = 1; one + j <= mx; ++j)
                if (isSubsequence(gen(i, j)))
                    ++a[i], --zro;
                else {
                    ok[i] = true;
                    --rem;
                    break;
                }
        }
        auto gen2 = [&](int pos, int cnt) {
            deque<int> res(cnt, 0);
            int last = 1;
            for (int i = pos - 1; ~i; --i) {
                if (last == 1) {
                    if (a[i] == 1)
                        res.push_front(0);
                    else if (a[i] > 1)
                        res.push_front(0), last = 0;
                }
                else {
                    res.push_front(1);
                    if (!a[i])
                        last = 1;
                }
            }
            last = 1;
            for (int i = pos; i < one; ++i) {
                if (last == 1) {
                    if (a[i + 1] == 1)
                        res.push_back(0);
                    else if (a[i + 1] > 1)
                        res.push_back(0), last = 0;
                }
                else {
                    res.push_back(1);
                    if (!a[i + 1])
                        last = 1;
                }
            }
            return vector<int>(all(res));
        };
        for (int i = 0; i < one + 1 && rem > 1 && zro; ++i)
            if (!ok[i]) {
                vector<int> tmp = gen2(i, a[i] + 1);
                while (tmp.size() <= mx) {
                    if (isSubsequence(tmp))
                        ++a[i], --zro;
                    else {
                        ok[i] = true;
                        --rem;
                        break;
                    }
                    tmp = gen2(i, a[i] + 1);
                }
            }
        for (int i = 0; i < one + 1; ++i)
            if (!ok[i])
                a[i] += zro, zro = 0;
        vector<int> ans;
        for (int i = 0; i < one + 1; ++i)
            ans.insert(ans.end(), a[i], 0), ans.push_back(1);
        ans.pop_back();
        return ans;
    }
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:117:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |                 while (tmp.size() <= mx) {
      |                        ~~~~~~~~~~~^~~~~
hidden.cpp:191:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  191 |                 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: 15 / 20
• Subtask 2: 0 / 80