QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #681124 | #2637. Factor-Free Tree | m5588ohammed | RE | 0ms | 0kb | C++20 | 3.2kb | 2024-10-27 01:26:29 | 2024-10-27 01:26:30 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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;
}
详细
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...