Submission #1139924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139924		12345678	Binary Subsequences (info1cup17_binary)	C++20	12.90 / 100	57 ms	76616 KiB

binary

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

struct node
{
    int a, b, cur, t, lvl;
    node *l, *r, *pa;
    node(int a, int b, int cur, int t, int lvl, node* pa): a(a), b(b), cur(cur), t(t), lvl(lvl), l(0), r(0), pa(pa){}
};
typedef node* pnode;

int Q, k, mx=2000, cnt[nx];
pair<int, pnode> res[nx];
pnode rt=new node(1, 1, 0, -1, 0, 0);
queue<pnode> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>Q;
    for (int i=1; i<=mx; i++) res[i]={(int)1e9, 0};
    q.push(rt);
    while (!q.empty())
    {
        auto x=q.front();
        q.pop();
        cnt[x->cur]++;
        res[x->cur]=min(res[x->cur], {x->lvl, x});
        if (x->cur+x->a<=mx) q.push(new node(x->a, x->a+x->b, x->cur+x->a, 0, x->lvl+1, x));
        if (x->cur+x->b<=mx) q.push(new node(x->a+x->b, x->b, x->cur+x->b, 1, x->lvl+1, x));
    }
    while (Q--) cin>>k, cout<<cnt[k]<<'\n'<<"-1"<<'\n';
}

• Subtask 1: 12.9 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18