oj.uz

Submission #138430

# Submission time Handle Problem Language Result Execution time Memory
138430 2019-07-29T22:30:49 Z silxikys Brunhilda’s Birthday (BOI13_brunhilda) C++14
12.8571 / 100
 1000 ms 48496 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5+5, INF = 2e9+9;
int m, Q;

int dp[10000005];

vector<int> primes;

struct Bag
{
    multiset<int> ms;
    int aux = 0;
    int max() {
        return *ms.rbegin() + aux;
    }
    void delta(int x) {
        aux += x;
    }
    void insert(int x) {
        ms.insert(x-aux);
    }
    void remove(int x) {
        auto it = ms.find(x-aux);
        ms.erase(it);
    }
};

struct Bag2
{
    set<pair<int,int>> ms;
    int aux = 0;
    void delta(int x) {
        aux += x;
    }
    pair<int,int> min() {
        return {ms.begin()->first+aux,ms.begin()->second};
    }
    void pop() {
        ms.erase(ms.begin());
    }
    void insert(pair<int,int> p) {
        ms.insert({p.first-aux,p.second});
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> m >> Q;
    for (int i = 0; i < m; i++) {
        int p; cin >> p;
        primes.push_back(p);
    }
    sort(primes.begin(),primes.end());
    int maxPrime = primes.back();
    for (int i = 1; i < maxPrime; i++) {
        dp[i] = 1;
    }
    Bag bag;
    Bag2 mods;
    for (int p: primes) {
        bag.insert((maxPrime-1)%p);
        mods.insert({p-((maxPrime-1)%p),p});
    }
    for (int i = maxPrime; i <= 10000000; i++) {
        bag.delta(1);
        mods.delta(-1);
        while (mods.min().first == 0) {
            int p = mods.min().second;
            mods.pop();
            mods.insert({p,p});
            bag.remove(p);
            bag.insert(0);
        }

        dp[i] = INF;
        int mxmod = bag.max();
        dp[i] = min(dp[i],1+dp[i-mxmod]);
        
        /*
        cout << i << " : " << mxmod << ' ';
        int mx = 0;
        for (int p: primes) {
            mx = max(mx,i%p);
        }
        cout << mx << '\n';
        */
    }

    /*
    for (int i = 1; i <= 50; i++) {
        cout << i << ": " << dp[i] << '\n';
    }
    */

    while (Q--) {
        int qi; cin >> qi;
        if (dp[qi] == INF) cout << "oo\n";
        else cout << dp[qi] << '\n';
    }
}

Subtask #1
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 39416 KB Output is correct
2 Execution timed out 1075 ms 18040 KB Time limit exceeded
3 Execution timed out 1086 ms 34856 KB Time limit exceeded
4 Correct 344 ms 39612 KB Output is correct
5 Correct 788 ms 39428 KB Output is correct
6 Correct 341 ms 39544 KB Output is correct
7 Execution timed out 1081 ms 34604 KB Time limit exceeded
8 Execution timed out 1086 ms 20088 KB Time limit exceeded
9 Execution timed out 1084 ms 12792 KB Time limit exceeded
10 Execution timed out 1072 ms 10340 KB Time limit exceeded
11 Execution timed out 1069 ms 14124 KB Time limit exceeded
12 Correct 264 ms 39704 KB Output is correct
13 Execution timed out 1087 ms 4984 KB Time limit exceeded
14 Execution timed out 1076 ms 5060 KB Time limit exceeded
15 Execution timed out 1080 ms 17376 KB Time limit exceeded
16 Execution timed out 1086 ms 18520 KB Time limit exceeded
17 Execution timed out 1075 ms 39528 KB Time limit exceeded
18 Correct 344 ms 39544 KB Output is correct

Subtask #2
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 39656 KB Time limit exceeded
2 Correct 295 ms 48496 KB Output is correct
3 Execution timed out 1074 ms 19124 KB Time limit exceeded
4 Execution timed out 1085 ms 19704 KB Time limit exceeded
5 Execution timed out 1078 ms 14968 KB Time limit exceeded
6 Execution timed out 1084 ms 22368 KB Time limit exceeded
7 Execution timed out 1071 ms 38244 KB Time limit exceeded
8 Execution timed out 1079 ms 23160 KB Time limit exceeded
9 Execution timed out 1065 ms 15696 KB Time limit exceeded
10 Execution timed out 1061 ms 18928 KB Time limit exceeded
11 Execution timed out 1054 ms 10340 KB Time limit exceeded
12 Execution timed out 1076 ms 9592 KB Time limit exceeded
13 Correct 915 ms 39752 KB Output is correct
14 Execution timed out 1076 ms 19720 KB Time limit exceeded
15 Execution timed out 1077 ms 11028 KB Time limit exceeded
16 Correct 286 ms 48372 KB Output is correct
17 Execution timed out 1071 ms 4988 KB Time limit exceeded
18 Execution timed out 1073 ms 32420 KB Time limit exceeded

Subtask #3
2.85714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 12280 KB Time limit exceeded
2 Execution timed out 1075 ms 10648 KB Time limit exceeded
3 Execution timed out 1086 ms 11320 KB Time limit exceeded
4 Execution timed out 1086 ms 8952 KB Time limit exceeded
5 Execution timed out 1022 ms 39792 KB Time limit exceeded
6 Execution timed out 1088 ms 6264 KB Time limit exceeded
7 Execution timed out 1086 ms 25716 KB Time limit exceeded
8 Execution timed out 1072 ms 12320 KB Time limit exceeded
9 Execution timed out 1085 ms 12408 KB Time limit exceeded
10 Execution timed out 1081 ms 8568 KB Time limit exceeded
11 Execution timed out 1077 ms 11640 KB Time limit exceeded
12 Execution timed out 1078 ms 6268 KB Time limit exceeded
13 Execution timed out 1085 ms 9464 KB Time limit exceeded
14 Execution timed out 1071 ms 9104 KB Time limit exceeded
15 Execution timed out 1071 ms 5496 KB Time limit exceeded
16 Execution timed out 1085 ms 4920 KB Time limit exceeded
17 Execution timed out 1082 ms 12024 KB Time limit exceeded
18 Execution timed out 1080 ms 10672 KB Time limit exceeded
19 Execution timed out 1083 ms 32424 KB Time limit exceeded
20 Execution timed out 1081 ms 10948 KB Time limit exceeded
21 Execution timed out 1077 ms 6520 KB Time limit exceeded
22 Execution timed out 1088 ms 18316 KB Time limit exceeded
23 Execution timed out 1078 ms 23616 KB Time limit exceeded
24 Correct 862 ms 40056 KB Output is correct
25 Execution timed out 1066 ms 8008 KB Time limit exceeded
26 Execution timed out 1086 ms 9128 KB Time limit exceeded
27 Execution timed out 1086 ms 18804 KB Time limit exceeded
28 Execution timed out 1076 ms 32248 KB Time limit exceeded
29 Execution timed out 1074 ms 19116 KB Time limit exceeded
30 Execution timed out 1081 ms 14816 KB Time limit exceeded
31 Execution timed out 1092 ms 23544 KB Time limit exceeded
32 Execution timed out 1074 ms 16496 KB Time limit exceeded
33 Correct 491 ms 39920 KB Output is correct
34 Execution timed out 1088 ms 25792 KB Time limit exceeded
35 Execution timed out 1087 ms 25952 KB Time limit exceeded
36 Execution timed out 1061 ms 17628 KB Time limit exceeded
37 Execution timed out 1086 ms 40496 KB Time limit exceeded
38 Execution timed out 1079 ms 5916 KB Time limit exceeded
39 Execution timed out 1081 ms 35228 KB Time limit exceeded
40 Execution timed out 1092 ms 7672 KB Time limit exceeded
41 Execution timed out 1074 ms 43460 KB Time limit exceeded
42 Execution timed out 1074 ms 4864 KB Time limit exceeded