QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #80478 | #2637. Factor-Free Tree | Walking_Dead | WA | 118ms | 31316kb | C++14 | 2.1kb | 2023-02-23 22:09:11 | 2023-02-23 22:09:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int n,a[MAXN],lef[MAXN],rig[MAXN];
#define MAXM 10000005
bool vis[MAXM];
int tot,prime[MAXM],lst[MAXM],mip[MAXM];
void Euler (int up){
for (Int i = 2;i <= up;++ i){
if (!vis[i]) prime[++ tot] = i,mip[i] = i;
for (Int j = 1;j <= tot && i * prime[j] <= up;++ j){
vis[i * prime[j]] = 1,mip[i * prime[j]] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
int fa[MAXN];
int divide (int l,int r){
if (l > r) return 0;
if (l == r) return l;
int rt = -1;
for (Int x = l,y = r;x <= y;){
if (lef[x] < l && rig[x] > r){rt = x;break;}
if (++ x > y) break;
if (lef[y] < l && rig[y] > r){rt = y;break;}
if (x > -- y) break;
}
if (rt == -1){puts ("impossible");exit (0);}
fa[divide (l,rt - 1)] = fa[divide (rt + 1,r)] = rt;
return rt;
}
signed main(){
// freopen ("1.in","r",stdin);
// freopen ("f1.out","w",stdout);
read (n);int mx = 0;
for (Int i = 1;i <= n;++ i) read (a[i]),mx = max (mx,a[i]);
Euler (mx);
for (Int i = 1;i <= n;++ i){
int v = a[i];
while (v > 1){
int p = mip[v];
chkmax (lef[i],lst[p]),lst[p] = i;
while (v % p == 0) v /= p;
}
}
for (Int i = 1;i <= mx;++ i) lst[i] = n + 1;
for (Int i = n;i >= 1;-- i){
int v = a[i];rig[i] = n + 1;
while (v > 1){
int p = mip[v];
chkmin (rig[i],lst[p]),lst[p] = i;
while (v % p == 0) v /= p;
}
}
int rt = divide (1,n);
for (Int i = 1;i <= n;++ i) write (fa[i]),putchar (' ');
putchar ('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 118ms
memory: 31316kb
input:
1000000 19 29 31 37 41 43 47 53 59 23 29 31 37 41 43 47 53 59 17 37 41 43 47 53 31 37 41 43 47 53 29 37 41 43 47 31 37 41 43 47 23 37 41 43 47 53 59 61 31 37 41 43 47 53 59 61 29 41 43 47 53 59 37 41 43 47 53 59 31 41 47 53 59 61 67 71 73 43 47 53 59 61 67 71 73 37 61 71 73 79 83 89 97 67 71 73 79 8...
output:
19 10 2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 999895 25 20 21 22 23 31 25 26 27 28 29 41 36 32 33 34 31 36 37 38 39 999880 49 42 43 44 45 46 47 57 49 50 51 52 53 54 55 41 63 58 59 60 61 69 63 64 65 66 67 57 86 78 71 72 73 74 75 76 70 78 79 80 81 82 83 84 69 101 94 88 89 90 91 92 87 94 95 96 97 98 99...
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 12636kb
input:
10 34033 56827 124799 25981 90371 129293 195581 175601 77867 102811
output:
0 1 2 3 4 5 6 7 8 9
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 12420kb
input:
100 4007 58067 87683 39181 1319 17659 105871 128981 112241 153733 98419 148867 162119 3877 28627 26681 10211 64591 146701 91183 192307 179119 81283 4729 65419 143197 37649 92567 48473 31277 182141 196991 17387 47491 183499 59107 61687 21323 160079 150401 16477 92809 182561 39113 151787 83557 173293 ...
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
result:
ok
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 12532kb
input:
1000 89417 156589 58309 7919 93497 100207 163981 176503 8887 69163 198823 102653 88609 13477 112603 94219 46831 34963 39113 190901 101723 121421 30553 51673 98129 17509 101021 28439 90023 16069 98299 66851 133321 587 154057 53381 67369 49277 1783 9109 7537 45137 32533 101627 137507 154789 29717 1386...
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 59 60 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 91 89 91 92 93 94 95 96 97 98 99 100 101 10...
result:
wrong answer Team has 17 children for index 60