oj.uz

Submission #31280

# Submission time Handle Problem Language Result Execution time Memory
31280 2017-08-17T20:51:58 Z imaxblue Brunhilda’s Birthday (BOI13_brunhilda) C++14
67.1429 / 100
 529 ms 81528 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, c, t, lo=(1 << 30), dp[10000005], f[10000005];
vector<bool> p=vector<bool>(10000000);
int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    cout.tie(0);
    cout.sync_with_stdio(0);
    cin >> n >> q;
    fox(l, n){
        cin >> x;
        p[x]=1;
        lo=min(lo, 10000000/x*x);
    }
    for(int l=2; l<=10000000; ++l){
        if (f[l]!=0) continue;
        for (int l2=l; l2<=10000000; l2+=l){
            if (p[l]) f[l2]=l;
        }
    }
    foxr1(l, 10000000){
        t=lo;
        lo=min(lo, l-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){
        cin >> x;
        if (dp[x]>=(1 << 30)){
            cout << "oo\n";
        }
        else {
            cout << dp[x] << endl;
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 81528 KB Output is correct
2 Correct 173 ms 81528 KB Output is correct
3 Correct 139 ms 81528 KB Output is correct
4 Correct 219 ms 81528 KB Output is correct
5 Correct 249 ms 81528 KB Output is correct
6 Correct 209 ms 81528 KB Output is correct
7 Correct 139 ms 81528 KB Output is correct
8 Correct 129 ms 81528 KB Output is correct
9 Correct 136 ms 81528 KB Output is correct
10 Correct 179 ms 81528 KB Output is correct
11 Correct 209 ms 81528 KB Output is correct
12 Correct 233 ms 81528 KB Output is correct
13 Correct 306 ms 81528 KB Output is correct
14 Correct 326 ms 81528 KB Output is correct
15 Correct 176 ms 81528 KB Output is correct
16 Correct 163 ms 81528 KB Output is correct
17 Correct 279 ms 81528 KB Output is correct
18 Correct 229 ms 81528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 81528 KB Output is correct
2 Correct 276 ms 81528 KB Output is correct
3 Correct 379 ms 81528 KB Output is correct
4 Correct 303 ms 81528 KB Output is correct
5 Correct 303 ms 81528 KB Output is correct
6 Correct 173 ms 81528 KB Output is correct
7 Correct 246 ms 81528 KB Output is correct
8 Correct 269 ms 81528 KB Output is correct
9 Correct 349 ms 81528 KB Output is correct
10 Correct 376 ms 81528 KB Output is correct
11 Correct 379 ms 81528 KB Output is correct
12 Correct 236 ms 81528 KB Output is correct
13 Correct 219 ms 81528 KB Output is correct
14 Correct 269 ms 81528 KB Output is correct
15 Correct 323 ms 81528 KB Output is correct
16 Correct 266 ms 81528 KB Output is correct
17 Correct 313 ms 81528 KB Output is correct
18 Correct 336 ms 81528 KB Output is correct

Subtask #3
27.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 81528 KB Output is correct
2 Correct 423 ms 81528 KB Output is correct
3 Correct 463 ms 81528 KB Output is correct
4 Runtime error 313 ms 81528 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 426 ms 81528 KB Execution timed out (wall clock limit exceeded)
6 Correct 436 ms 81528 KB Output is correct
7 Correct 456 ms 81528 KB Output is correct
8 Correct 373 ms 81528 KB Output is correct
9 Correct 416 ms 81528 KB Output is correct
10 Correct 359 ms 81528 KB Output is correct
11 Correct 346 ms 81528 KB Output is correct
12 Correct 359 ms 81528 KB Output is correct
13 Runtime error 459 ms 81528 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 243 ms 81528 KB Execution timed out (wall clock limit exceeded)
15 Correct 343 ms 81528 KB Output is correct
16 Correct 289 ms 81528 KB Output is correct
17 Correct 273 ms 81528 KB Output is correct
18 Correct 483 ms 81528 KB Output is correct
19 Correct 193 ms 81528 KB Output is correct
20 Correct 459 ms 81528 KB Output is correct
21 Runtime error 313 ms 81528 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 513 ms 81528 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 396 ms 81528 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 309 ms 81528 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 376 ms 81528 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 359 ms 81528 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 519 ms 81528 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 353 ms 81528 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 509 ms 81528 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 476 ms 81528 KB Execution timed out (wall clock limit exceeded)
31 Correct 373 ms 81528 KB Output is correct
32 Runtime error 369 ms 81528 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 316 ms 81528 KB Execution timed out (wall clock limit exceeded)
34 Correct 386 ms 81528 KB Output is correct
35 Runtime error 343 ms 81528 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 529 ms 81528 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 393 ms 81528 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 463 ms 81528 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 369 ms 81528 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 356 ms 81528 KB Execution timed out (wall clock limit exceeded)
41 Correct 346 ms 81528 KB Output is correct
42 Runtime error 396 ms 81528 KB Execution timed out (wall clock limit exceeded)