oj.uz

Submission #155737

# Submission time Handle Problem Language Result Execution time Memory
155737 2019-09-30T07:27:56 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 959 ms 118904 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

const int N = 1e7 + 5;

int dp[2 * N], p[2 * N], used[N];

deque<int> dq;

int m, q;

int main() {
    scanf("%d%d", &m, &q);
    for(int i = 0; i < N; i++)
        p[i] = 0;
    for(int i = 1; i <= N - 5; i++)
        dp[i] = inf;
    for(int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        for(int l = 0; l < N; l++) {
            if(x * l >= N) break;
            p[x * l] = max(p[x * l], x);
        }
    }
    for(int i = 0; i <= N - 5; i++) {
    	//if(i <= 6)
    	//cout << used[i] << " " << dq.size() << " " << i << "\n";
    	for(int j = 1; j <= used[i]; j++)
            dq.pop_back();
        if(dq.size() > 0)
            dp[i] = dq.back();
        if(p[i] != 0)
    		 dq.push_front(dp[i] + 1);
        if(i + p[i] > N - 5) continue;
        used[i + p[i]] ++;
    }
    for(int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        if(dp[x] == inf)
            cout << "oo\n";
        else
            cout << dp[x] << "\n";
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 117840 KB Output isn't correct
2 Incorrect 253 ms 117752 KB Output isn't correct
3 Incorrect 225 ms 117900 KB Output isn't correct
4 Incorrect 196 ms 117760 KB Output isn't correct
5 Incorrect 216 ms 117788 KB Output isn't correct
6 Incorrect 181 ms 117840 KB Output isn't correct
7 Incorrect 241 ms 117776 KB Output isn't correct
8 Incorrect 251 ms 117756 KB Output isn't correct
9 Incorrect 322 ms 117752 KB Output isn't correct
10 Incorrect 376 ms 117776 KB Output isn't correct
11 Incorrect 351 ms 117796 KB Output isn't correct
12 Incorrect 184 ms 117556 KB Output isn't correct
13 Incorrect 470 ms 117816 KB Output isn't correct
14 Incorrect 509 ms 117752 KB Output isn't correct
15 Incorrect 298 ms 117752 KB Output isn't correct
16 Incorrect 266 ms 117764 KB Output isn't correct
17 Incorrect 264 ms 117824 KB Output isn't correct
18 Incorrect 220 ms 117760 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 117768 KB Output isn't correct
2 Incorrect 326 ms 118136 KB Output isn't correct
3 Incorrect 783 ms 118044 KB Output isn't correct
4 Incorrect 282 ms 117740 KB Output isn't correct
5 Incorrect 479 ms 118008 KB Output isn't correct
6 Incorrect 242 ms 117752 KB Output isn't correct
7 Incorrect 269 ms 117764 KB Output isn't correct
8 Incorrect 301 ms 117724 KB Output isn't correct
9 Incorrect 476 ms 118204 KB Output isn't correct
10 Incorrect 528 ms 118136 KB Output isn't correct
11 Incorrect 530 ms 117948 KB Output isn't correct
12 Incorrect 363 ms 117756 KB Output isn't correct
13 Incorrect 204 ms 117752 KB Output isn't correct
14 Incorrect 281 ms 117868 KB Output isn't correct
15 Incorrect 486 ms 117988 KB Output isn't correct
16 Incorrect 284 ms 118136 KB Output isn't correct
17 Incorrect 479 ms 117768 KB Output isn't correct
18 Incorrect 501 ms 118264 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 629 ms 118188 KB Output isn't correct
2 Incorrect 638 ms 118200 KB Output isn't correct
3 Incorrect 780 ms 118208 KB Output isn't correct
4 Incorrect 677 ms 118228 KB Output isn't correct
5 Incorrect 641 ms 118520 KB Output isn't correct
6 Incorrect 767 ms 118172 KB Output isn't correct
7 Incorrect 640 ms 118620 KB Output isn't correct
8 Incorrect 625 ms 118136 KB Output isn't correct
9 Incorrect 625 ms 118092 KB Output isn't correct
10 Incorrect 436 ms 117864 KB Output isn't correct
11 Incorrect 426 ms 117860 KB Output isn't correct
12 Incorrect 520 ms 118016 KB Output isn't correct
13 Incorrect 795 ms 118352 KB Output isn't correct
14 Incorrect 683 ms 118608 KB Output isn't correct
15 Incorrect 547 ms 117928 KB Output isn't correct
16 Incorrect 603 ms 117952 KB Output isn't correct
17 Incorrect 545 ms 118008 KB Output isn't correct
18 Incorrect 603 ms 117996 KB Output isn't correct
19 Incorrect 311 ms 117924 KB Output isn't correct
20 Incorrect 710 ms 118236 KB Output isn't correct
21 Incorrect 767 ms 118532 KB Output isn't correct
22 Incorrect 914 ms 118904 KB Output isn't correct
23 Incorrect 639 ms 118368 KB Output isn't correct
24 Incorrect 540 ms 118364 KB Output isn't correct
25 Incorrect 734 ms 118236 KB Output isn't correct
26 Incorrect 702 ms 118288 KB Output isn't correct
27 Incorrect 917 ms 118516 KB Output isn't correct
28 Incorrect 580 ms 118308 KB Output isn't correct
29 Incorrect 959 ms 118544 KB Output isn't correct
30 Incorrect 894 ms 118616 KB Output isn't correct
31 Incorrect 575 ms 118360 KB Output isn't correct
32 Incorrect 607 ms 118136 KB Output isn't correct
33 Incorrect 490 ms 118164 KB Output isn't correct
34 Incorrect 636 ms 118520 KB Output isn't correct
35 Incorrect 575 ms 118308 KB Output isn't correct
36 Incorrect 879 ms 118648 KB Output isn't correct
37 Incorrect 647 ms 118592 KB Output isn't correct
38 Incorrect 770 ms 118136 KB Output isn't correct
39 Incorrect 578 ms 118256 KB Output isn't correct
40 Incorrect 762 ms 118360 KB Output isn't correct
41 Incorrect 723 ms 118500 KB Output isn't correct
42 Incorrect 872 ms 118372 KB Output isn't correct