답안 #74561 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74561	2018-09-03T17:21:50 Z	SpeedOfMagic	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	1000 ms	49300 KB

brunhilda

/** 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
//you want to set 2 functions: f(int a, int b) and segTreeNode::update(int val) and 1 parameter: nothing

const int nothing = 0; //nothing means that f(x, nothing) = x

struct segTreeNode {
    int val = nothing;

    segTreeNode(int _val) : val(_val) {}

    void update(int _val) { //function that updates node based on val
        this -> val = _val;
    }
};

vector<segTreeNode> segTree;
int n, tot;

int f(int a, int b) { //f - query you need to calculate, but for two values
    return max(segTree[a].val, segTree[b].val);
}

void update(int nodeToUpdate, int value, int cur = 1, int ll = 1, int rr = tot) {
    if (ll == rr) {
        segTree[cur].update(value);
        return;
    }

    int p = (ll + rr) / 2;

    if (nodeToUpdate <= p)
        update(nodeToUpdate, value, cur * 2, ll, p);
    else
        update(nodeToUpdate, value, cur * 2 + 1, p + 1, rr);

    segTree[cur] = f(cur * 2, cur * 2 + 1);
}

int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) {
    if (l > r)
        return nothing;

    if (l == ll && r == rr)
        return segTree[cur].val;

    int mid = (ll + rr) / 2;
    return f(query(l, min(r, mid), cur * 2, ll, mid), query(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr));
}

void init(vector<int> vals) {
    n = vals.size();

    tot = n;
    while (tot & (tot - 1))
        tot++;

    segTree = vector<segTreeNode>(tot * 2, segTreeNode(nothing));

    for (int i = 0; i < n; i++)
        segTree[i + tot].val = vals[i];

    for (int i = tot - 1; i; i--)
        segTree[i] = f(i * 2, i * 2 + 1);
}

const long long N = 1e7 + 1;
const int LIM = 100;
int dp[N];

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

    vint primes;

    priority_queue<pair<int, int>> nxt;
    int p[m];
    rep(i, 0, m) {
        get p[i];
        if (p[i] > LIM)
            nxt.push({-p[i], 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;

    init(vint(m, 1));

    rep(i, 1, N) {
        while (!nxt.empty() && -nxt.top().fs == i) {
            int j = nxt.top().sc;
            int val = -nxt.top().fs;
            nxt.pop();
            nxt.push({-(val + p[j]), j});

            update(j + 1, -pen);
        }
        int d = query(1, tot);
        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;}

Compilation message

brunhilda.cpp: In function 'void run()':
brunhilda.cpp:130:9: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
     int cur[m];
         ^~~

Subtask #1
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	57 ms	39416 KB	Output isn't correct
2	Incorrect	199 ms	39492 KB	Output isn't correct
3	Incorrect	56 ms	39576 KB	Output isn't correct
4	Incorrect	184 ms	39716 KB	Output isn't correct
5	Incorrect	56 ms	39716 KB	Output isn't correct
6	Incorrect	62 ms	39728 KB	Output isn't correct
7	Incorrect	58 ms	39728 KB	Output isn't correct
8	Incorrect	56 ms	39728 KB	Output isn't correct
9	Incorrect	56 ms	39728 KB	Output isn't correct
10	Incorrect	61 ms	39728 KB	Output isn't correct
11	Incorrect	61 ms	39744 KB	Output isn't correct
12	Incorrect	141 ms	39760 KB	Output isn't correct
13	Execution timed out	1076 ms	39760 KB	Time limit exceeded
14	Execution timed out	1074 ms	39760 KB	Time limit exceeded
15	Incorrect	127 ms	39760 KB	Output isn't correct
16	Incorrect	208 ms	39760 KB	Output isn't correct
17	Incorrect	277 ms	39840 KB	Output isn't correct
18	Incorrect	182 ms	39904 KB	Output isn't correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	501 ms	40132 KB	Output isn't correct
2	Incorrect	572 ms	42664 KB	Output isn't correct
3	Execution timed out	1067 ms	42664 KB	Time limit exceeded
4	Incorrect	679 ms	42664 KB	Output isn't correct
5	Execution timed out	1071 ms	42664 KB	Time limit exceeded
6	Incorrect	295 ms	42664 KB	Output isn't correct
7	Incorrect	471 ms	42664 KB	Output isn't correct
8	Incorrect	528 ms	42664 KB	Output isn't correct
9	Execution timed out	1076 ms	42664 KB	Time limit exceeded
10	Execution timed out	1081 ms	42664 KB	Time limit exceeded
11	Execution timed out	1076 ms	42664 KB	Time limit exceeded
12	Incorrect	782 ms	42664 KB	Output isn't correct
13	Incorrect	189 ms	42664 KB	Output isn't correct
14	Incorrect	684 ms	42664 KB	Output isn't correct
15	Execution timed out	1078 ms	42664 KB	Time limit exceeded
16	Incorrect	605 ms	42664 KB	Output isn't correct
17	Execution timed out	1086 ms	42664 KB	Time limit exceeded
18	Execution timed out	1075 ms	42664 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1076 ms	42664 KB	Time limit exceeded
2	Execution timed out	1070 ms	42664 KB	Time limit exceeded
3	Execution timed out	1088 ms	42664 KB	Time limit exceeded
4	Incorrect	846 ms	42664 KB	Output isn't correct
5	Execution timed out	1062 ms	44228 KB	Time limit exceeded
6	Execution timed out	1082 ms	44228 KB	Time limit exceeded
7	Execution timed out	1084 ms	44228 KB	Time limit exceeded
8	Execution timed out	1076 ms	44228 KB	Time limit exceeded
9	Execution timed out	1091 ms	44228 KB	Time limit exceeded
10	Execution timed out	1091 ms	44228 KB	Time limit exceeded
11	Incorrect	967 ms	44228 KB	Output isn't correct
12	Execution timed out	1086 ms	44228 KB	Time limit exceeded
13	Execution timed out	1074 ms	44228 KB	Time limit exceeded
14	Incorrect	270 ms	44228 KB	Output isn't correct
15	Execution timed out	1082 ms	44228 KB	Time limit exceeded
16	Execution timed out	1076 ms	44228 KB	Time limit exceeded
17	Execution timed out	1076 ms	44228 KB	Time limit exceeded
18	Execution timed out	1082 ms	44228 KB	Time limit exceeded
19	Incorrect	359 ms	44228 KB	Output isn't correct
20	Execution timed out	1081 ms	44228 KB	Time limit exceeded
21	Incorrect	623 ms	44228 KB	Output isn't correct
22	Execution timed out	1075 ms	44228 KB	Time limit exceeded
23	Execution timed out	1064 ms	44228 KB	Time limit exceeded
24	Incorrect	483 ms	44228 KB	Output isn't correct
25	Execution timed out	1082 ms	44228 KB	Time limit exceeded
26	Incorrect	871 ms	44228 KB	Output isn't correct
27	Execution timed out	1079 ms	44228 KB	Time limit exceeded
28	Incorrect	414 ms	44228 KB	Output isn't correct
29	Execution timed out	1083 ms	44228 KB	Time limit exceeded
30	Execution timed out	1070 ms	44228 KB	Time limit exceeded
31	Incorrect	614 ms	44884 KB	Output isn't correct
32	Incorrect	840 ms	45480 KB	Output isn't correct
33	Incorrect	327 ms	45480 KB	Output isn't correct
34	Execution timed out	1066 ms	45480 KB	Time limit exceeded
35	Incorrect	649 ms	46328 KB	Output isn't correct
36	Execution timed out	1076 ms	46328 KB	Time limit exceeded
37	Execution timed out	1022 ms	49300 KB	Time limit exceeded
38	Execution timed out	1070 ms	49300 KB	Time limit exceeded
39	Incorrect	673 ms	49300 KB	Output isn't correct
40	Execution timed out	1065 ms	49300 KB	Time limit exceeded
41	Execution timed out	1078 ms	49300 KB	Time limit exceeded
42	Execution timed out	1085 ms	49300 KB	Time limit exceeded

답안 #74561

Compilation message

Subtask #1 0 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
0 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0