結果

問題 No.490 yukiソート
ユーザー IL_msta
提出日時 2017-03-10 22:29:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 6,259 bytes
コンパイル時間 1,500 ms
コンパイル使用メモリ 125,836 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 09:58:44
合計ジャッジ時間 2,605 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma region GNUC
//以下を参考にした
//https://yukicoder.me/wiki/auto_vectorization
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif
#pragma endregion
#define _USE_MATH_DEFINES
#pragma region
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <fstream>
#include <random>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
/////////
//定数
const int INF = (int)1e9;
const int MOD = (int)1e9+7;
const LL LINF = (LL)1e18;
/////////
using namespace::std;
/////////
#pragma region Math
// 最大公約数
template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}
//inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}
// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
//inline T lcm(T a, T b){return a * b / gcd(a, b);}
#pragma endregion //math
#pragma region
template<class T>
void UNIQUE(vector<T>& vec){
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end() );
}
#pragma endregion // sort erase unique
////////////////////////////////
struct edge{int to;LL cost;};
edge make_edge(int to,LL cost){
    edge ret = {to,cost};
    return ret;
}
#pragma region //グラフ
void dijkstra(int root,int V,vector<LL>& dist,
    vector< vector<edge> > G    ){
    priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > que;
    dist.assign(V,LINF);
    dist[root] = 0;
    que.push(pair<LL,int>(0,root));//距離、頂点番号
    while( !que.empty() ){
        pair<LL,int> p = que.top();que.pop();
        int v = p.second;
        if( dist[v] < p.first ) continue;
        for(int i=0;i < (int)G[v].size();++i){
            edge e = G[v][i];
            if( dist[e.to] > dist[v] + e.cost ){
                dist[e.to] = dist[v] + e.cost;
                que.push(pair<LL,int>(dist[e.to],e.to));
            }
        }
    }
}
#pragma endregion //ダイクストラ法:O(|E|log|V|)
#pragma region //グラフ
void warshall_floyd(vector<vector<LL> >& dist,int V,const LL INF=LINF){
    for(int k=0;k<V;++k){
        for(int i=0;i<V;++i){
            if( dist[i][k] >= INF ) continue;
            for(int j=0;j<V;++j){
                if( dist[k][j] >= INF )continue;
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
}
#pragma endregion //ワーシャルフロイド:O(|V|**3)
#pragma region 
//http://sugarknri.hatenablog.com/entry/2016/07/16/165715
//LL inv[1000010];
void makeinv(vector<LL>& inv,const LL P){
    int i;
    inv = vector<LL>(1000010,0);
    inv[1]=1;
    for(i=2;i<=1000000;i++){
        inv[i] = inv[P%i] * (P-P/i)%P;//OVF
    }
}
ULL nCk(ULL N,ULL k){
    static vector<LL> inv;
    if( inv.size() == 0 ){
        makeinv(inv,MOD);
    }
    k = min(k,N-k);
    if( k == 0 ){return 1;}
    if( k == 1 ){return N%MOD;}
    ULL ret = 1;
    for(int i=1;i<=k;++i){
        ret *= ((N+1-i)*inv[i])%MOD;//OVF
        ret %= MOD;
    }
    return ret;
}
#pragma endregion //組み合わせnCk(,10^5)
#pragma region CGL
class Point{
public:
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
    Point   operator +  (Point p){return Point(add(x,p.x),add(y,p.y));}
    void    operator += (Point p){x=add(x,p.x);y=add(y,p.y);}
    Point   operator -  (Point p){return Point(add(x,-p.x),add(y,-p.y));}
    void    operator -= (Point p){x=add(x,-p.x);y=add(y,-p.y);}
    Point   operator *  (double a){return Point(x*a,y*a);}
    double  operator *  (Point p){return dot(p);}
    Point   operator /  (double a){return Point(x/a,y/a);}
    double norm(){return sqrt(x*x+y*y);}
    double dot(Point p){return add(x*p.x,y*p.y);}
    double rot(Point p){return add(x*p.y,-y*p.x);}
    double add(double a,double b){
        double EPS = 1e-10;
        if( abs(a+b) < EPS*(abs(a)+abs(b)) ){
            return 0;
        }
        return a+b;
    }
};
istream& operator>>(istream& in,Point& P){
    in >> P.x >> P.y;
    return in;
}
//線分p1-p2上に点qがあるか判定
bool on_seg(Point p1,Point p2,Point q){
    return (p1-q).rot(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}
Point intersection(Point p1,Point p2,Point q1,Point q2){
    return p1+(p2-p1)*((q2-q1).rot(q1-p1)/(q2-q1).rot(p2-p1));
}
enum PointPotion{ON_SEGMENT,COUNTER_CLOCKWISE,ONLINE_BACK,CLOCKWISE,ONLINE_FRONT};
PointPotion ccw(Point A,Point B,Point C){
    B -= A;C -=A;
    if( B.rot(C) > 0 ) return COUNTER_CLOCKWISE;
    if( B.rot(C) < 0 ) return CLOCKWISE;
    if( B.dot(C) < 0 ) return ONLINE_BACK;
    if( B.norm() < C.norm() ) return ONLINE_FRONT;
    return ON_SEGMENT;
}
#pragma endregion //class Point
#pragma region
//辞書順で比較
bool cmp_x(const Point& p,const Point& q){
    if( p.x != q.x ) return p.x < q.x;
    return p.y < q.y;
}
//凸包を求める
vector<Point> convex_hull(vector<Point> ps,int n){
    sort(ps.begin(),ps.end(), cmp_x);
    int k = 0;//凸包の頂点数
    vector<Point> qs(n*2);//構築中の凸包
    //下側の凸包の作成
    for(int i=0;i<n;++i){
        while(k>1 && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){
            k--;
        }
        qs[k++] = ps[i];
    }
    //上側凸包の作成
    for(int i=n-2,t=k;i>=0;i--){
        while(k>t && (qs[k-1]-qs[k-2]).rot(ps[i]-qs[k-1]) <=0){
            k--;
        }
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}
#pragma endregion //凸包
#pragma region 
template<class T,class U>
istream& operator>>(istream& in,pair<T,U> P){
    in >> P.first >> P.second;
    return in;
}
#pragma endregion //cin pair<T,U>
#pragma region 
#pragma endregion //
const double PI = acos(-1.0);
const double EPS = 1e-9;
void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0;i<N;++i){
        cin >> A[i];
    }
    bool up = true;
    while(up){
        up = false;
        for(int i=0;i<2*N-3;++i){
            for(int p=0;p<N-1;++p){
                int q = i-p;
                if( q < 0 || N <= q ) continue;
                if( p >= q ) break;
                if( A[p] > A[q] ){
                    up = true;
                    swap(A[p],A[q] );
                }
            }
            
        }
    }
    for(int i=0;i<N;++i){
        cout << A[i];
        if( i+1<N ) cout << " ";
        else cout << endl;
    }
}
#pragma region main
signed main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//小数を10進数表示
    cout << setprecision(16);//小数点以下の桁数を指定
    
    solve();
}
#pragma endregion //main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0