oj.uz

Submission #31285

# Submission time Handle Problem Language Result Execution time Memory
31285 2017-08-17T21:09:07 Z imaxblue Brunhilda’s Birthday (BOI13_brunhilda) C++14
63.3333 / 100
 1000 ms 81368 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define foxr1(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)

int n, q, x, t, l2, k, lo=(1 << 30), dp[10000005], f[10000005];
vector<bool> p=vector<bool>(10000005);
int main(){
    scanf("%i%i", &n, &q);
    fox(l, n){
        scanf("%i", &x);
        p[x]=1;
        lo=min(lo, 10000000/x*x);
    }
    for(int l=2; l<=10000000; l++){
        if (f[l]!=0) continue;
        if (p[l]) k=l; else k=-1;
        for (l2=l; l2<=10000000; l2+=l){
            f[l2]=max(f[l2], k);
        }
    }
    foxr1(l, 10000000){
        t=lo;
        lo=min(lo, l-max(0, f[l]));
        f[l]=t;
        //cout << f[l] << endl;
    }
    fox1(l, 10000000){
        if (f[l]==l) dp[l]=(1 << 30);
        dp[l]=dp[f[l]]+1;
    }
    fox(l, q){
        scanf("%i", &x);
        if (dp[x]>=(1 << 30)){
            printf("oo\n");
        }
        else {
            printf("%i\n", dp[x]);
        }
    }
    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:29:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &n, &q);
                          ^
brunhilda.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &x);
                        ^
brunhilda.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &x);
                        ^

Subtask #1
12.2222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 81368 KB Execution timed out
2 Correct 693 ms 81368 KB Output is correct
3 Correct 853 ms 81368 KB Output is correct
4 Execution timed out 1000 ms 81368 KB Execution timed out
5 Execution timed out 1000 ms 81368 KB Execution timed out
6 Execution timed out 1000 ms 81368 KB Execution timed out
7 Correct 893 ms 81368 KB Output is correct
8 Correct 656 ms 81368 KB Output is correct
9 Correct 503 ms 81368 KB Output is correct
10 Correct 469 ms 81368 KB Output is correct
11 Correct 669 ms 81368 KB Output is correct
12 Execution timed out 1000 ms 81368 KB Execution timed out
13 Correct 439 ms 81368 KB Output is correct
14 Correct 413 ms 81368 KB Output is correct
15 Correct 823 ms 81368 KB Output is correct
16 Correct 586 ms 81368 KB Output is correct
17 Execution timed out 1000 ms 81368 KB Execution timed out
18 Execution timed out 1000 ms 81368 KB Execution timed out

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 81368 KB Execution timed out
2 Execution timed out 1000 ms 81368 KB Execution timed out
3 Correct 383 ms 81368 KB Output is correct
4 Execution timed out 1000 ms 81368 KB Execution timed out
5 Correct 769 ms 81368 KB Output is correct
6 Correct 889 ms 81368 KB Output is correct
7 Execution timed out 1000 ms 81368 KB Execution timed out
8 Execution timed out 1000 ms 81368 KB Execution timed out
9 Correct 613 ms 81368 KB Output is correct
10 Correct 386 ms 81368 KB Output is correct
11 Correct 399 ms 81368 KB Output is correct
12 Correct 723 ms 81368 KB Output is correct
13 Execution timed out 1000 ms 81368 KB Execution timed out
14 Execution timed out 1000 ms 81368 KB Execution timed out
15 Correct 449 ms 81368 KB Output is correct
16 Execution timed out 1000 ms 81368 KB Execution timed out
17 Correct 299 ms 81368 KB Output is correct
18 Correct 576 ms 81368 KB Output is correct

Subtask #3
40.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 81368 KB Output is correct
2 Correct 389 ms 81368 KB Output is correct
3 Correct 409 ms 81368 KB Output is correct
4 Correct 676 ms 81368 KB Output is correct
5 Execution timed out 1000 ms 81368 KB Execution timed out
6 Correct 439 ms 81368 KB Output is correct
7 Correct 949 ms 81368 KB Output is correct
8 Correct 313 ms 81368 KB Output is correct
9 Correct 393 ms 81368 KB Output is correct
10 Correct 813 ms 81368 KB Output is correct
11 Execution timed out 1000 ms 81368 KB Execution timed out
12 Correct 489 ms 81368 KB Output is correct
13 Correct 429 ms 81368 KB Output is correct
14 Correct 483 ms 81368 KB Output is correct
15 Correct 423 ms 81368 KB Output is correct
16 Correct 363 ms 81368 KB Output is correct
17 Correct 716 ms 81368 KB Output is correct
18 Correct 389 ms 81368 KB Output is correct
19 Execution timed out 1000 ms 81368 KB Execution timed out
20 Correct 346 ms 81368 KB Output is correct
21 Correct 389 ms 81368 KB Output is correct
22 Correct 499 ms 81368 KB Output is correct
23 Execution timed out 1000 ms 81368 KB Execution timed out
24 Execution timed out 1000 ms 81368 KB Execution timed out
25 Correct 573 ms 81368 KB Output is correct
26 Correct 616 ms 81368 KB Output is correct
27 Correct 359 ms 81368 KB Output is correct
28 Execution timed out 1000 ms 81368 KB Execution timed out
29 Correct 853 ms 81368 KB Output is correct
30 Execution timed out 1000 ms 81368 KB Execution timed out
31 Execution timed out 1000 ms 81368 KB Execution timed out
32 Execution timed out 1000 ms 81368 KB Execution timed out
33 Execution timed out 1000 ms 81368 KB Execution timed out
34 Execution timed out 1000 ms 81368 KB Execution timed out
35 Execution timed out 1000 ms 81368 KB Execution timed out
36 Correct 466 ms 81368 KB Output is correct
37 Execution timed out 1000 ms 81368 KB Execution timed out
38 Correct 523 ms 81368 KB Output is correct
39 Execution timed out 1000 ms 81368 KB Execution timed out
40 Correct 619 ms 81368 KB Output is correct
41 Correct 773 ms 81368 KB Output is correct
42 Correct 406 ms 81368 KB Output is correct