QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #80487 | #2637. Factor-Free Tree | Walking_Dead | WA | 122ms | 31164kb | C++14 | 2.2kb | 2023-02-23 22:17:57 | 2023-02-23 22:17:59 |
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);}
/*
int ls = divide (l,rt - 1),rs = divide (rt + 1,r);
fa[ls] = fa[rs] = rt;
*/
int ls = divide (l,rt - 1);
fa[divide (rt + 1,r)] = fa[ls] = 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: 0
Wrong Answer
time: 122ms
memory: 31164kb
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 8 8 8 8 8 8 8 17 10 17 17 17 17 17 17 17 999895 25 23 23 23 23 31 25 29 29 29 29 41 36 34 34 34 31 36 39 39 39 999880 49 47 47 47 47 47 47 57 49 55 55 55 55 55 55 41 63 61 61 61 61 69 63 67 67 67 67 57 86 78 76 76 76 76 76 76 84 78 84 84 84 84 84 84 69 101 94 92 92 92 92 92 99 94 99 99 99 99 9...
result:
wrong answer Team has 7 children for index 8