Recently i was viewing some of the questions of the external contest section and this question caught my attention. Question link. I have implemented a solution but it gives WA as verdict. My solution:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define repu(v,s,e) for(ll v=s;v<e;v++)
#define repd(v,s,e) for(ll v=s;v>e;v--)
#define ip(n,a) repu(i,0,n)cin>>a[i];
#define mod 1000000007
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
ll bs(ll y,ll coef){
ll start=1,end=y;
while(start<=end){
ll x=(start+end)/2;
if(x*(coef+x)==y) return x;
if(x*(coef+x)<y) start=x+1;
else end=x-1;
}
return 0;
}
int main(){
fastio
ll t,n,x;
cin>>t;
while(t--){
cin>>n;
ll count[10001]={0};
ll val[10001],cnt[10001],posi[10001],pos=0;
repu(i,0,n*n){cin>>x;count[x]++;}
repd(i,10000,0) if(count[i]) val[pos]=i,posi[i]=pos,cnt[pos]=count[i],pos++;
ll ans[n],c=0;
repu(i,0,pos){
if(cnt[i]){
ll coef=0;
repu(j,0,i) if(cnt[j] && val[j]%val[i]==0) coef+=2*cnt[j];
ll x=bs(cnt[i],coef);
repu(j,0,x) ans[c++]=val[i];
cnt[i]=x;
repu(j,0,i) if(cnt[j] && val[j]%val[i]!=0){
ll g=gcd(val[j],val[i]);
cnt[posi[g]]-=2*cnt[j]*cnt[i];
}
}
if(c==n) break;
}
repu(i,0,n) cout<<ans[n-i-1]<<" "; cout<<"\n";
}
}
Can anyone find me edge cases? And any other way to solve this question?