oj.uz

Submission #74636

# Submission time Handle Problem Language Result Execution time Memory
74636 2018-09-05T12:23:15 Z SpeedOfMagic Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 807 ms 263168 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const long long N = 1e7 + 1;
const int LIM = 20;
vint erato[N];
int dp[N];

void run() {
    int m, q;
    read(m, q);

    vint primes;
    int p[m];
    rep(i, 0, m) {
        get p[i];
        if (p[i] > LIM)
            erato[p[i]].pb(p[i]);
        else
            primes.pb(p[i]);
    }

    long long mul = 1;
    rep(i, 0, m) {
        mul *= p[i];
        if (mul > N) {
            mul = 1e9;
            break;
        }
    }

    dp[0] = 0;

    int cur[m];
    rep(i, 0, m)
        cur[i] = 1;
    int pen = 0;
    map<int, int> mx;
    rep(i, 0, m)
        if (p[i] > LIM)
            mx[1]++;
    rep(i, 1, N) {
        while (!erato[i].empty()) {
            int j = erato[i].back();
            erato[i].pop_back();
            erato[i + j].pb(j);

            mx[cur[j]]--;
            if (mx[cur[j]] == 0)
                mx.erase(cur[j]);
            cur[j] = -pen;
            mx[cur[j]]++;
        }
        int d = 0;
        if (!mx.empty())
            d = ((*mx.rbegin()).fs) + pen;
        for (int j : primes)
            d = max(d, i % j);
        dp[i] = dp[i - d] + 1;

        pen++;
    }

    rep(i, 0, q) {
        int n;
        get n;
        if (n >= mul)
            put "oo";
        else
            put dp[n];
        eol;
    }
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 581 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 377 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 586 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 581 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 366 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 339 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 571 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 582 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 575 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 566 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 583 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 599 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 592 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 599 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 592 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 585 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 630 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 598 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 657 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 694 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 586 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 631 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 595 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 592 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 597 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 686 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 692 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 669 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 571 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 593 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 590 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 633 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 667 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 623 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 763 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 659 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 660 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 638 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 583 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 656 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 619 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 698 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 659 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 634 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 600 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 605 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 616 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 660 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 577 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 592 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 585 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 651 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 673 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 695 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 644 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 600 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 729 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 694 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 667 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 678 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 617 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 807 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 664 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 787 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 741 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 616 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 621 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 603 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 764 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 660 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 702 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 678 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 614 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 572 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 612 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 724 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 590 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)