# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
74483 | 2018-09-02T12:02:40 Z | SpeedOfMagic | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 437 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 = 42; vint erato[N]; int dp[N]; void run() { int m, q; read(m, q); int p[m]; rep(i, 0, m) { get p[i]; if (p[i] > LIM) for (int j = 1; j * p[i] < N; j++) erato[j * p[i]].pb(i); } long long mul = 1; rep(i, 0, m) { mul *= p[i]; if (mul > N) { mul = 1e9; break; } } vint primes; for (int i : {2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41}) for (int j : p) if (i == j) { primes.pb(i); 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) { for (int j : erato[i]) { 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;}
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 293 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Runtime error | 298 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Runtime error | 367 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
4 | Runtime error | 354 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
5 | Runtime error | 292 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Runtime error | 317 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
7 | Runtime error | 331 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
8 | Runtime error | 401 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
9 | Runtime error | 437 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
10 | Runtime error | 314 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
11 | Runtime error | 278 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
12 | Runtime error | 383 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
13 | Runtime error | 277 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
14 | Runtime error | 292 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
15 | Runtime error | 301 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
16 | Runtime error | 303 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
17 | Runtime error | 287 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
18 | Runtime error | 374 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 350 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Runtime error | 351 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Runtime error | 279 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
4 | Runtime error | 347 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
5 | Runtime error | 290 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Runtime error | 320 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
7 | Runtime error | 357 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
8 | Runtime error | 329 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
9 | Runtime error | 311 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
10 | Runtime error | 277 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
11 | Runtime error | 288 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
12 | Runtime error | 334 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
13 | Runtime error | 369 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
14 | Runtime error | 359 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
15 | Runtime error | 293 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
16 | Runtime error | 299 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
17 | Runtime error | 329 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
18 | Runtime error | 305 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 308 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Runtime error | 269 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Runtime error | 277 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
4 | Runtime error | 319 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
5 | Runtime error | 333 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
6 | Runtime error | 289 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
7 | Runtime error | 303 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
8 | Runtime error | 286 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
9 | Runtime error | 290 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
10 | Runtime error | 289 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
11 | Runtime error | 323 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
12 | Runtime error | 314 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
13 | Runtime error | 287 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
14 | Runtime error | 302 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
15 | Runtime error | 320 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
16 | Runtime error | 306 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
17 | Runtime error | 356 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
18 | Runtime error | 266 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
19 | Runtime error | 389 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
20 | Runtime error | 312 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
21 | Runtime error | 269 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
22 | Runtime error | 289 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
23 | Runtime error | 367 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
24 | Runtime error | 369 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
25 | Runtime error | 292 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
26 | Runtime error | 292 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
27 | Runtime error | 321 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
28 | Runtime error | 329 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
29 | Runtime error | 302 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
30 | Runtime error | 302 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
31 | Runtime error | 303 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
32 | Runtime error | 318 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
33 | Runtime error | 385 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
34 | Runtime error | 305 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
35 | Runtime error | 317 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
36 | Runtime error | 284 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
37 | Runtime error | 348 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
38 | Runtime error | 312 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
39 | Runtime error | 369 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
40 | Runtime error | 290 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
41 | Runtime error | 305 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
42 | Runtime error | 316 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |