Submission #1865108
Source Code Expand
#include"bits/stdc++.h"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
const int maxn = 100010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}
template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}
int n,m;
int A[maxn];
vector<int> G[maxn];
int vi[maxn];
int has[2010][2010],l[2010];
bool cmp(int x,int y){
return A[x]<A[y];
}
void dfs(int u){
if(vi[u])return;
vi[u]=1;
has[m][++l[m]]=A[u];
for(auto v:G[u])dfs(v);
}
void Work(){
REP(i,1,n)if(!vi[i]){
m++;
dfs(i);
reverse(has[m]+1,has[m]+l[m]+1);
}
REP(i,1,n){
int mx=0,p=0;
REP(j,1,m)if(has[j][l[j]]>mx)mx=has[j][l[j]],p=j;
printf("%d ",mx);
l[p]--;
}
}
void Init(){
read(n);
REP(i,1,n)read(A[i]);
REP(i,1,n)REP(j,1,n)if(i!=j&&__gcd(A[i],A[j])!=1)G[i].PB(j);
REP(i,1,n)sort(G[i].begin(),G[i].end(),cmp);
}
int main(){
Init();
Work();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Rearranging |
User |
yanQval |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2311 Byte |
Status |
WA |
Exec Time |
601 ms |
Memory |
19968 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt |
All |
sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
WA |
600 ms |
14080 KB |
in10.txt |
WA |
601 ms |
14464 KB |
in11.txt |
WA |
435 ms |
5504 KB |
in12.txt |
WA |
438 ms |
5504 KB |
in13.txt |
WA |
435 ms |
5504 KB |
in14.txt |
WA |
437 ms |
5504 KB |
in15.txt |
WA |
437 ms |
5504 KB |
in16.txt |
WA |
596 ms |
19968 KB |
in17.txt |
WA |
595 ms |
19968 KB |
in18.txt |
WA |
592 ms |
19840 KB |
in19.txt |
WA |
595 ms |
19840 KB |
in2.txt |
WA |
597 ms |
13952 KB |
in20.txt |
WA |
594 ms |
19840 KB |
in21.txt |
WA |
336 ms |
17792 KB |
in22.txt |
WA |
337 ms |
17792 KB |
in23.txt |
WA |
338 ms |
17792 KB |
in24.txt |
WA |
336 ms |
17792 KB |
in25.txt |
WA |
336 ms |
17792 KB |
in26.txt |
WA |
437 ms |
5504 KB |
in27.txt |
WA |
437 ms |
5504 KB |
in28.txt |
WA |
434 ms |
5504 KB |
in29.txt |
WA |
438 ms |
5504 KB |
in3.txt |
WA |
596 ms |
13696 KB |
in30.txt |
WA |
437 ms |
5504 KB |
in31.txt |
AC |
2 ms |
4480 KB |
in32.txt |
AC |
2 ms |
4480 KB |
in33.txt |
AC |
2 ms |
4480 KB |
in34.txt |
AC |
389 ms |
17792 KB |
in35.txt |
AC |
388 ms |
17792 KB |
in36.txt |
WA |
470 ms |
6912 KB |
in37.txt |
WA |
470 ms |
6912 KB |
in38.txt |
WA |
471 ms |
6912 KB |
in39.txt |
WA |
473 ms |
6912 KB |
in4.txt |
WA |
596 ms |
13824 KB |
in40.txt |
WA |
470 ms |
6912 KB |
in41.txt |
WA |
470 ms |
6912 KB |
in42.txt |
WA |
472 ms |
6912 KB |
in43.txt |
WA |
470 ms |
6912 KB |
in44.txt |
WA |
471 ms |
6784 KB |
in45.txt |
WA |
472 ms |
6912 KB |
in5.txt |
WA |
596 ms |
13568 KB |
in6.txt |
WA |
599 ms |
14336 KB |
in7.txt |
WA |
600 ms |
14464 KB |
in8.txt |
WA |
600 ms |
14080 KB |
in9.txt |
WA |
595 ms |
13696 KB |
sample1.txt |
AC |
2 ms |
4480 KB |
sample2.txt |
AC |
2 ms |
4480 KB |