fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e3+1,M=2e5+1;
  4. vector<int> V[N],G[M];
  5. vector<int> S;
  6. int n,A[N],Nodes[N],In[M],k,m,done[N],s,ok,cnt,ans[N];
  7. void Deco(int x,int y){
  8.     int l=x;
  9.     for(int i=2;i*i<=x;i++){
  10.         if(l%i==0){
  11.             V[y].push_back(x/i);
  12.             G[x/i].push_back(y);
  13.             In[x/i]++;
  14.             Nodes[y]++;
  15.         }
  16.         while(l%i==0)
  17.             l/=i;
  18.     }
  19.     if(l!=1){
  20.         V[y].push_back(x/l);
  21.         G[x/l].push_back(y);
  22.         In[x/l]++;
  23.         Nodes[y]++;
  24.     }
  25. }
  26. void bestIn(){
  27.     k=N,m=-1;
  28.     for(int i=0;i<S.size();i++){
  29.         if(In[S[i]]<k && In[S[i]]!=0){
  30.             k=In[S[i]];
  31.             m=S[i];
  32.         }
  33.     }
  34.     if(k!=1)
  35.         return ;
  36.     In[m]=0;
  37.     for(int i=0;i<G[m].size();i++){
  38.         if(!done[G[m][i]]){
  39.             s=G[m][i];
  40.             break;
  41.         }
  42.     }
  43.     done[s]=1;
  44.     ans[s]=A[s]/m;
  45.     cnt--;
  46.     for(int i=0;i<V[s].size();i++){
  47.         if(In[V[s][i]]>0){
  48.             In[V[s][i]]--;
  49.         }
  50.     }
  51. }
  52. void bestNode(){
  53.     k=N,m=-1;
  54.     for(int i=1;i<=n;i++){
  55.         if(Nodes[i]<k && !done[i]){
  56.             m=i;
  57.             k=Nodes[i];
  58.         }
  59.     }
  60.     if(k==0){
  61.         printf("-1\n");
  62.         ok=1;
  63.         return ;
  64.     }
  65.     done[m]=1;
  66.     cnt--;
  67.     s=0;
  68.     for(int i=0;i<V[m].size();i++){
  69.         if(In[V[m][i]]){
  70.             if(!s){
  71.                 s=V[m][i];
  72.             }
  73.             else
  74.                 In[V[m][i]]--;
  75.         }
  76.     }
  77.     In[s]=0;
  78.     ans[m]=A[m]/s;
  79.     for(int i=0;i<G[s].size();i++){
  80.         if(!done[G[s][i]] && Nodes[G[s][i]]>0){
  81.             Nodes[G[s][i]]--;
  82.         }
  83.     }
  84. }
  85. int main()
  86. {
  87.     scanf("%d",&n);
  88.     for(int i=1;i<=n;i++){
  89.         scanf("%d",&A[i]);
  90.         Deco(A[i],i);
  91.     }
  92.     for(int i=1;i<M;i++){
  93.         if(In[i])
  94.             S.push_back(i);
  95.     }
  96.     cnt=n;
  97.     while(cnt){
  98.         k=1;
  99.         while(k==1 && cnt){
  100.             bestIn();
  101.         }
  102.         if(cnt){
  103.            bestNode();
  104.            if(ok)
  105.                 return 0;
  106.         }
  107.     }
  108.     for(int i=1;i<=n;i++){
  109.         printf("%d ",ans[i]);
  110.     }
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 7816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u34hZx
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!