| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 558893 | 2022-05-08T23:38:04 Z | Olympia | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 630 ms | 30296 KB |
#include <bits/stdc++.h>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = 1e9; T comb(T a, T b) { return min(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int M, Q; cin >> M >> Q;
vector<int> p(M);
Seg<int> st;
st.init(M + 1);
map<int,int> primes;
for (int i = 0; i < M; i++) {
cin >> p[i];
st.upd(i, 0);
}
sort(p.begin(), p.end());
for (int i = 0; i < M; i++) {
primes[p[i]] = i;
st.upd(i, 0);
}
int mx = 1000000;
int res[mx];
bool isPrime[mx];
for (int i = 0; i < mx; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
int lpf[mx];
for (int i = 0; i < mx; i++) {
lpf[i] = -1;
}
for (int i = 2; i < mx; i++) {
if (isPrime[i]) {
for (int j = 2 * i; j < mx; j += i) {
isPrime[j] = false;
if (primes.count(i)) lpf[j] = primes[i];
}
if (primes.count(i)) lpf[i] = primes[i];
}
}
for (int i = 1; i < mx; i++) {
int ans = 1e9;
if (lpf[i] == -1) {
ans = st.query(0, M - 1) + 1;
} else {
vector<int> invalid;
invalid.push_back(-1);
int x = i;
while (lpf[x] != -1) {
invalid.push_back(lpf[x]);
int a = p[lpf[x]];
while (x % a == 0) x /= a;
}
sort(invalid.begin(), invalid.end());
invalid.push_back(p.size());
for (int j = 0; j < (int)invalid.size() - 1; j++) {
if (invalid[j] + 1 <= invalid[j + 1] - 1) {
ans = min(ans, st.query(invalid[j] + 1, invalid[j + 1] - 1) + 1);
}
}
for (int j: invalid) {
if (j >= 0 && j < (int)p.size()) {
st.upd(j, ans);
}
}
}
res[i] = ans;
}
while (Q--) {
int x;
cin >> x;
if (res[x] == (int)1e9) {
cout << "oo\n";
} else {
cout << res[x] << '\n';
}
}
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 40 ms | 9124 KB | Output isn't correct |
| 2 | Correct | 163 ms | 9044 KB | Output is correct |
| 3 | Correct | 112 ms | 9100 KB | Output is correct |
| 4 | Correct | 50 ms | 9120 KB | Output is correct |
| 5 | Correct | 63 ms | 9112 KB | Output is correct |
| 6 | Incorrect | 41 ms | 9108 KB | Output isn't correct |
| 7 | Correct | 112 ms | 9100 KB | Output is correct |
| 8 | Correct | 150 ms | 9044 KB | Output is correct |
| 9 | Correct | 186 ms | 9100 KB | Output is correct |
| 10 | Correct | 205 ms | 9164 KB | Output is correct |
| 11 | Correct | 153 ms | 9104 KB | Output is correct |
| 12 | Correct | 49 ms | 9044 KB | Output is correct |
| 13 | Correct | 366 ms | 9172 KB | Output is correct |
| 14 | Correct | 356 ms | 9172 KB | Output is correct |
| 15 | Correct | 163 ms | 9120 KB | Output is correct |
| 16 | Correct | 163 ms | 9108 KB | Output is correct |
| 17 | Correct | 83 ms | 9104 KB | Output is correct |
| 18 | Correct | 50 ms | 9120 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 118 ms | 19656 KB | Execution killed with signal 11 |
| 2 | Runtime error | 187 ms | 29072 KB | Execution killed with signal 11 |
| 3 | Runtime error | 566 ms | 26552 KB | Execution killed with signal 11 |
| 4 | Runtime error | 161 ms | 18628 KB | Execution killed with signal 11 |
| 5 | Runtime error | 345 ms | 24280 KB | Execution killed with signal 11 |
| 6 | Runtime error | 170 ms | 18388 KB | Execution killed with signal 11 |
| 7 | Runtime error | 122 ms | 19668 KB | Execution killed with signal 11 |
| 8 | Runtime error | 133 ms | 18332 KB | Execution killed with signal 11 |
| 9 | Runtime error | 420 ms | 26764 KB | Execution killed with signal 11 |
| 10 | Runtime error | 573 ms | 26532 KB | Execution killed with signal 11 |
| 11 | Runtime error | 519 ms | 22996 KB | Execution killed with signal 11 |
| 12 | Runtime error | 285 ms | 18440 KB | Execution killed with signal 11 |
| 13 | Runtime error | 108 ms | 18624 KB | Execution killed with signal 11 |
| 14 | Runtime error | 163 ms | 18552 KB | Execution killed with signal 11 |
| 15 | Runtime error | 451 ms | 23216 KB | Execution killed with signal 11 |
| 16 | Runtime error | 188 ms | 29188 KB | Execution killed with signal 11 |
| 17 | Runtime error | 400 ms | 18632 KB | Execution killed with signal 11 |
| 18 | Runtime error | 468 ms | 30296 KB | Execution killed with signal 11 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 476 ms | 24212 KB | Execution killed with signal 11 |
| 2 | Runtime error | 565 ms | 24488 KB | Execution killed with signal 11 |
| 3 | Runtime error | 566 ms | 24208 KB | Execution killed with signal 11 |
| 4 | Runtime error | 281 ms | 18640 KB | Execution killed with signal 11 |
| 5 | Runtime error | 204 ms | 29948 KB | Execution killed with signal 11 |
| 6 | Runtime error | 379 ms | 19188 KB | Execution killed with signal 11 |
| 7 | Runtime error | 351 ms | 30096 KB | Execution killed with signal 11 |
| 8 | Runtime error | 485 ms | 24212 KB | Execution killed with signal 11 |
| 9 | Runtime error | 478 ms | 24212 KB | Execution killed with signal 11 |
| 10 | Runtime error | 275 ms | 18924 KB | Execution killed with signal 11 |
| 11 | Runtime error | 219 ms | 18732 KB | Execution killed with signal 11 |
| 12 | Runtime error | 362 ms | 18972 KB | Execution killed with signal 11 |
| 13 | Runtime error | 471 ms | 21756 KB | Execution killed with signal 11 |
| 14 | Runtime error | 239 ms | 18200 KB | Execution killed with signal 11 |
| 15 | Runtime error | 403 ms | 18832 KB | Execution killed with signal 11 |
| 16 | Runtime error | 452 ms | 19124 KB | Execution killed with signal 11 |
| 17 | Runtime error | 387 ms | 23524 KB | Execution killed with signal 11 |
| 18 | Runtime error | 552 ms | 24536 KB | Execution killed with signal 11 |
| 19 | Runtime error | 155 ms | 18888 KB | Execution killed with signal 11 |
| 20 | Runtime error | 556 ms | 24176 KB | Execution killed with signal 11 |
| 21 | Runtime error | 275 ms | 18252 KB | Execution killed with signal 11 |
| 22 | Runtime error | 585 ms | 30160 KB | Execution killed with signal 11 |
| 23 | Runtime error | 172 ms | 21764 KB | Execution killed with signal 11 |
| 24 | Runtime error | 95 ms | 18388 KB | Execution killed with signal 11 |
| 25 | Runtime error | 279 ms | 18584 KB | Execution killed with signal 11 |
| 26 | Runtime error | 276 ms | 18648 KB | Execution killed with signal 11 |
| 27 | Runtime error | 630 ms | 30096 KB | Execution killed with signal 11 |
| 28 | Runtime error | 127 ms | 18372 KB | Execution killed with signal 11 |
| 29 | Runtime error | 499 ms | 30224 KB | Execution killed with signal 11 |
| 30 | Runtime error | 410 ms | 26536 KB | Execution killed with signal 11 |
| 31 | Runtime error | 153 ms | 18708 KB | Execution killed with signal 11 |
| 32 | Runtime error | 179 ms | 18632 KB | Execution killed with signal 11 |
| 33 | Runtime error | 83 ms | 18400 KB | Execution killed with signal 11 |
| 34 | Runtime error | 367 ms | 30084 KB | Execution killed with signal 11 |
| 35 | Runtime error | 151 ms | 18432 KB | Execution killed with signal 11 |
| 36 | Runtime error | 616 ms | 28988 KB | Execution killed with signal 11 |
| 37 | Runtime error | 215 ms | 30028 KB | Execution killed with signal 11 |
| 38 | Runtime error | 405 ms | 19180 KB | Execution killed with signal 11 |
| 39 | Runtime error | 124 ms | 18468 KB | Execution killed with signal 11 |
| 40 | Runtime error | 363 ms | 19380 KB | Execution killed with signal 11 |
| 41 | Runtime error | 389 ms | 30092 KB | Execution killed with signal 11 |
| 42 | Runtime error | 433 ms | 18624 KB | Execution killed with signal 11 |