Submission #156502

#	Time	Username	Problem	Language	Result	Execution time	Memory
156502		combi1k1	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	40.63 / 100	1097 ms	119516 KiB

brunhilda

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e7 + 1;
const int   inf = 1e9 + 7;

int t[N << 1];
int f[N];

void Min(int &x,int y)  {
    if (x > y)
        x = y;
}
void upd(int l,int r,int v) {
    l += N - 1;
    r += N;
    for(; l < r ; l >>= 1, r >>= 1) {
        if (l & 1)  Min(t[l++],v);
        if (r & 1)  Min(t[--r],v);
    }
}
int get(int p)  {
    int ans = inf;
    for(p += N - 1 ; p ; p >>= 1)
        Min(ans,t[p]);
    return  ans;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int m;  cin >> m;
    int Q;  cin >> Q;

    for(int i = 1 ; i < N + N ; ++i)
        t[i] = inf;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        for(int j = 0 ; j < N ; j += x)
            upd(j,min(j + x - 1,N),j);
    }

    for(int i = 1 ; i < N ; ++i)    {
        int p = get(i);
        if (p < i)
            f[i] = f[p] + 1;
        else
            f[i] = inf;
    }

    for(int i = 0 ; i < Q ; ++i)    {
        int x;  cin >> x;
        if (f[x] >= inf)
            cout << "oo\n";
        else
            cout << f[x] << "\n";
    }
}

• Subtask 1: 17.77777777777778 / 20
• Subtask 2: 10 / 20
• Subtask 3: 12.857142857142858 / 60