Submission #1102224
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
print_tuple<Cdr...>(os,t);
os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
print_tuple<Args...>(os<<'(',t);
return os<<')';
}
template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
os<<'[';
for(auto i=begin(c);i!=end(c);++i)
os<<(i==begin(c)?"":" ")<<*i;
return os<<']';
}
constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;
vi merge(const vi& a,const vi& us,const vi& vs)
{
vi res;
int i=0,j=0;
while(i<us.size()&&j<vs.size())
res.push_back(a[us[i]]>=a[vs[j]]?us[i++]:vs[j++]);
res.insert(end(res),i+all(us));
res.insert(end(res),j+all(vs));
return res;
}
vi dfs(const vvi& g,const vi& a,int u,vi& vis)
{
vis[u]=1;
vi res;
for(int v:g[u]) if(!vis[v])
res=merge(a,res,dfs(g,a,v,vis));
res.insert(begin(res),u);
return res;
}
int main()
{
for(int n;cin>>n&&n;){
vi a(n);
rep(i,n) cin>>a[i];
sort(all(a));
vvi g(n);
rep(i,n) repi(j,i+1,n) if(__gcd(a[i],a[j])!=1){
g[i].push_back(j);
g[j].push_back(i);
}
vi vis(n),res;
rep(i,n) if(!vis[i])
res=merge(a,res,dfs(g,a,i,vis));
rep(i,n) cout<<a[res[i]]<<" \n"[i==n-1];
}
}
Submission Info
Submission Time |
|
Task |
E - Rearranging |
User |
lyoz |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2227 Byte |
Status |
AC |
Exec Time |
275 ms |
Memory |
17920 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 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 |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
273 ms |
10240 KB |
in10.txt |
AC |
273 ms |
10880 KB |
in11.txt |
AC |
224 ms |
1792 KB |
in12.txt |
AC |
225 ms |
1792 KB |
in13.txt |
AC |
224 ms |
1792 KB |
in14.txt |
AC |
224 ms |
1792 KB |
in15.txt |
AC |
224 ms |
1792 KB |
in16.txt |
AC |
249 ms |
17792 KB |
in17.txt |
AC |
249 ms |
17920 KB |
in18.txt |
AC |
248 ms |
17792 KB |
in19.txt |
AC |
249 ms |
17792 KB |
in2.txt |
AC |
273 ms |
10240 KB |
in20.txt |
AC |
250 ms |
17920 KB |
in21.txt |
AC |
169 ms |
384 KB |
in22.txt |
AC |
169 ms |
384 KB |
in23.txt |
AC |
170 ms |
384 KB |
in24.txt |
AC |
169 ms |
384 KB |
in25.txt |
AC |
169 ms |
384 KB |
in26.txt |
AC |
224 ms |
1792 KB |
in27.txt |
AC |
225 ms |
1792 KB |
in28.txt |
AC |
223 ms |
1792 KB |
in29.txt |
AC |
226 ms |
1792 KB |
in3.txt |
AC |
275 ms |
10112 KB |
in30.txt |
AC |
225 ms |
1792 KB |
in31.txt |
AC |
3 ms |
256 KB |
in32.txt |
AC |
3 ms |
256 KB |
in33.txt |
AC |
3 ms |
256 KB |
in34.txt |
AC |
198 ms |
384 KB |
in35.txt |
AC |
198 ms |
384 KB |
in36.txt |
AC |
237 ms |
3328 KB |
in37.txt |
AC |
237 ms |
3456 KB |
in38.txt |
AC |
238 ms |
3328 KB |
in39.txt |
AC |
240 ms |
3456 KB |
in4.txt |
AC |
273 ms |
10112 KB |
in40.txt |
AC |
237 ms |
3328 KB |
in41.txt |
AC |
237 ms |
3328 KB |
in42.txt |
AC |
240 ms |
3328 KB |
in43.txt |
AC |
239 ms |
3328 KB |
in44.txt |
AC |
238 ms |
3328 KB |
in45.txt |
AC |
238 ms |
3328 KB |
in5.txt |
AC |
272 ms |
9856 KB |
in6.txt |
AC |
275 ms |
10752 KB |
in7.txt |
AC |
273 ms |
10880 KB |
in8.txt |
AC |
273 ms |
10368 KB |
in9.txt |
AC |
273 ms |
10112 KB |
sample1.txt |
AC |
3 ms |
256 KB |
sample2.txt |
AC |
3 ms |
256 KB |