fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main(){
  6.   int n;
  7.   cin >> n;
  8.   vector<int> p(n);
  9.   for(auto &nx : p){cin >> nx;}
  10.   next_permutation(p.begin(),p.end());
  11.  
  12.   set<int> st;
  13.   for(int i=1;i<=n;i++){st.insert(i);}
  14.  
  15.   vector<int> res={p[0]};
  16.   st.erase(p[0]);
  17.   bool fl=true;
  18.   for(int i=1;i<n;i++){
  19.     if(fl){
  20.       int lef=-1;
  21.       auto it=st.lower_bound(res.back());
  22.       if(it!=st.begin()){
  23.         it--;
  24.         lef=(*it);
  25.       }
  26.  
  27.       if(lef<=p[i]){
  28.         res.push_back(p[i]);
  29.         st.erase(p[i]);
  30.       }
  31.       else{
  32.         res.push_back(lef);
  33.         st.erase(lef);
  34.         fl=false;
  35.       }
  36.     }
  37.     else{
  38.       auto it=st.lower_bound(res.back());
  39.       if(it!=st.begin()){
  40.         it--;
  41.       }
  42.       res.push_back(*it);
  43.       st.erase(it);
  44.     }
  45.   }
  46.  
  47.   for(int i=0;i<n;i++){
  48.     if(i){cout << " ";}
  49.     cout << res[i];
  50.   }
  51. }
  52.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
2 4 5 3 1
stdout
copy 
2 5 4 3 1
https://ideone.com/DJzJMR
language:
C++14 (gcc 8.3)
created:
142 days 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!