Submission #1236835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236835		Solikha	Hidden Sequence (info1cup18_hidden)	C++20	59 / 100	3 ms	424 KiB

hidden

#include "bits/stdc++.h"
#include "grader.h"
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

vector < int > findSequence (int n)
{
    vector<int> v;
    for(int i = 0; i < n / 2; i++){
        v.pb(0);
        if(isSubsequence(v) == 0){
            v.pop_back(); break;
        }
    }

    if(v.size() == n / 2){
        v.clear();
        v.pb(1);
        while(isSubsequence(v) == 1) v.pb(1);
        v.pop_back();
    }

    int k = v.size();
    int x = 1 - v[0]; // ? lar

    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> cnt(k + 1);
    for(int i = 0; i <= k; i++) pq.emplace(0, i);

    auto make_r = [&](int id) -> vector<int>{
        vector<int> vi(id, 1 - x);
        for(int i = 0; i < cnt[id]; i++) vi.pb(x);
        for(int i = id + 1; i <= k; i++) vi.pb(1 - x);
        return vi;
    };

    while(!pq.empty()){
        auto [c, id] = pq.top();
        pq.pop();
        if(pq.empty()){
            int sum = accumulate(all(cnt), 0ll);
            cnt[id] = n - sum - k + c;
            break;
        }

        cnt[id]++;
        if(isSubsequence(make_r(id)) == 0) cnt[id]--;
        else pq.emplace(cnt[id], id);
    }
  
    v.clear();
    for(int i = 0; i <= k; i ++){
        for(int j = 0; j < cnt[i]; j++) v.pb(x);
        if(i < k) v.pb(1 - x);
    }
    return v;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 20
• Subtask 2: 44 / 80