QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #681126 | #2637. Factor-Free Tree | m5588ohammed | RE | 0ms | 0kb | C++20 | 3.2kb | 2024-10-27 01:31:03 | 2024-10-27 01:31:04 |
answer
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int L[1000001],R[1000001],prime[10000001],arr[1000001],parent[1000001];
int n;
map <int,int> mp;
set <int> st;
vector <int> v[1000001];
void buildL(int i){
int a=arr[i];
while(a!=1){
int div=prime[a];
if(L[i]==0) L[i]=mp[div];
else L[i]=max(L[i],mp[div]);
while(a%div==0) a/=div;
mp[div]=i;
}
return;
}
void buildR(int i){
int a=arr[i];
while(a!=1){
int div=prime[a];
if(R[i]==0) R[i]=mp[div];
else R[i]=min(R[i],mp[div]);
while(a%div==0) a/=div;
mp[div]=i;
}
if(R[i]==0) R[i]=n+1;
return;
}
void build(){
for(int i=2;i<=10000000;i++){
if(prime[i]!=0) continue;
for(int j=i;j<=10000000;j+=i) if(prime[j]==0) prime[j]=i;
}
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
buildL(i);
}
mp.clear();
for(int i=n;i>=1;i--){
buildR(i);
v[L[i]].push_back(i);
v[R[i]].push_back(i);
}
for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
return;
}
void imp(){
cout<<"impossible";
exit(0);
}
int check(int i){
if(L[i]==0&&R[i]==n+1) return 1;
else return 0;
}
void solve(int l,int r,int pre){
if(l>r) return;
if(st.size()==0) imp();
int rt=*st.begin(),siz1=rt-l,siz2=r-rt;
set <int> st2;
parent[rt]=pre;
st.erase(rt);
if(siz1<=siz2){
for(int i=l;i<rt;i++){
if(R[i]>=rt) R[i]=n+1;
if(check(i)==1){
st.erase(i);
st2.insert(i);
}
int l1=0,r1=v[i].size()-1,idx=v[i].size();
while(l1<=r1){
int mid=(l1+r1)/2;
if(v[i][mid]>rt){
idx=mid;
r1=mid-1;
}
else l1=mid+1;
}
for(int j=idx;j<v[i].size();j++){
if(v[i][j]>r) break;
L[v[i][j]]=0;
if(check(v[i][j])==1) st.insert(v[i][j]);
}
}
solve(rt+1,r,rt);
swap(st2,st);
solve(l,rt-1,rt);
}
else{
for(int i=rt;i<=r;i--){
if(L[i]<=rt) L[i]=0;
if(check(i)==1){
st.erase(i);
st2.insert(i);
}
int l1=0,r1=v[i].size()-1,idx=0;
while(l1<=r1){
int mid=(l1+r1)/2;
if(v[i][mid]<rt){
idx=mid;
l1=mid+1;
}
else r1=mid-1;
}
for(int j=idx;j>=0;j--){
if(v[i][j]<l) break;
R[v[i][j]]=n+1;
if(check(v[i][j])==1) st.insert(v[i][j]);
}
}
solve(l,rt-1,rt);
swap(st2,st);
solve(rt+1,r,rt);
}
return;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
build();
for(int i=1;i<=n;i++) if(check(i)==1) st.insert(i);
solve(1,n,0);
for(int i=1;i<=n;i++) cout<<parent[i]<<" ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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...