oj.uz

Submission #138429

# Submission time Handle Problem Language Result Execution time Memory
138429 2019-07-29T22:29:16 Z silxikys Brunhilda’s Birthday (BOI13_brunhilda) C++14
21.4286 / 100
 105 ms 44572 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 <= 10000; 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 4 ms 424 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4984 KB Output isn't correct
2 Incorrect 101 ms 44572 KB Output isn't correct
3 Incorrect 56 ms 16884 KB Output isn't correct
4 Incorrect 4 ms 1016 KB Output isn't correct
5 Incorrect 42 ms 10484 KB Output isn't correct
6 Incorrect 3 ms 760 KB Output isn't correct
7 Incorrect 12 ms 4984 KB Output isn't correct
8 Incorrect 3 ms 632 KB Output isn't correct
9 Incorrect 50 ms 12404 KB Output isn't correct
10 Incorrect 56 ms 17012 KB Output isn't correct
11 Incorrect 28 ms 7800 KB Output isn't correct
12 Incorrect 3 ms 760 KB Output isn't correct
13 Incorrect 5 ms 2552 KB Output isn't correct
14 Incorrect 4 ms 988 KB Output isn't correct
15 Incorrect 28 ms 7516 KB Output isn't correct
16 Incorrect 89 ms 44468 KB Output isn't correct
17 Incorrect 4 ms 888 KB Output isn't correct
18 Incorrect 89 ms 29556 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 9208 KB Output isn't correct
2 Incorrect 52 ms 8312 KB Output isn't correct
3 Incorrect 47 ms 9208 KB Output isn't correct
4 Incorrect 35 ms 1400 KB Output isn't correct
5 Incorrect 105 ms 27608 KB Output isn't correct
6 Incorrect 38 ms 1884 KB Output isn't correct
7 Incorrect 87 ms 21408 KB Output isn't correct
8 Incorrect 51 ms 9336 KB Output isn't correct
9 Incorrect 51 ms 9332 KB Output isn't correct
10 Incorrect 19 ms 1528 KB Output isn't correct
11 Incorrect 20 ms 1272 KB Output isn't correct
12 Incorrect 21 ms 1404 KB Output isn't correct
13 Incorrect 42 ms 6520 KB Output isn't correct
14 Incorrect 26 ms 632 KB Output isn't correct
15 Incorrect 22 ms 1400 KB Output isn't correct
16 Incorrect 21 ms 1528 KB Output isn't correct
17 Incorrect 46 ms 7928 KB Output isn't correct
18 Incorrect 53 ms 8312 KB Output isn't correct
19 Incorrect 22 ms 3680 KB Output isn't correct
20 Incorrect 47 ms 9208 KB Output isn't correct
21 Incorrect 29 ms 632 KB Output isn't correct
22 Incorrect 99 ms 16244 KB Output isn't correct
23 Incorrect 50 ms 7416 KB Output isn't correct
24 Incorrect 34 ms 1144 KB Output isn't correct
25 Incorrect 35 ms 1016 KB Output isn't correct
26 Incorrect 35 ms 1400 KB Output isn't correct
27 Incorrect 89 ms 16676 KB Output isn't correct
28 Incorrect 23 ms 1400 KB Output isn't correct
29 Incorrect 99 ms 16184 KB Output isn't correct
30 Incorrect 75 ms 11452 KB Output isn't correct
31 Incorrect 35 ms 2168 KB Output isn't correct
32 Incorrect 35 ms 1272 KB Output isn't correct
33 Incorrect 34 ms 1528 KB Output isn't correct
34 Incorrect 86 ms 21364 KB Output isn't correct
35 Incorrect 24 ms 1404 KB Output isn't correct
36 Incorrect 99 ms 15348 KB Output isn't correct
37 Incorrect 104 ms 27516 KB Output isn't correct
38 Incorrect 39 ms 1912 KB Output isn't correct
39 Incorrect 36 ms 1272 KB Output isn't correct
40 Incorrect 39 ms 2296 KB Output isn't correct
41 Correct 104 ms 39000 KB Output is correct
42 Incorrect 23 ms 1016 KB Output isn't correct