Submission #464758

#	Time	Username	Problem	Language	Result	Execution time	Memory
464758		JovanB	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	92.06 / 100	1093 ms	40752 KiB

brunhilda

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 10000000;

int dp[N+5];
int tren;
queue <pair <int, int>> q[2];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int m, qrs;
    cin >> m >> qrs;
    for(int i=1; i<=m; i++){
        int x;
        cin >> x;
        q[0].push({0, x});
    }
    for(int i=1; i<=N; i++){
        queue <int> divs;
        while(!q[0].empty()){
            int j, x;
            tie(j, x) = q[0].front();
            if(j + x < i) q[(tren != dp[j+x])].push({j + x, x});
            else if(j + x <= i) divs.push(x);
            else break;
            q[0].pop();
        }
        if(q[0].empty()) swap(q[0], q[1]), tren++;
        while(!q[0].empty()){
            int j, x;
            tie(j, x) = q[0].front();
            if(j + x < i) q[(tren != dp[j+x])].push({j + x, x});
            else if(j + x <= i) divs.push(x);
            else break;
            q[0].pop();
        }
        if(q[0].empty()) break;
        dp[i] = tren + 1;
        while(!divs.empty()) q[1].push({i, divs.front()}), divs.pop();
    }
    while(qrs--){
        int x;
        cin >> x;
        if(!dp[x]) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 17.77777777777778 / 20
• Subtask 3: 54.285714285714285 / 60