fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define pb emplace_back 
  5. #define mp make_pair
  6. #define fi first 
  7. #define se second 
  8. #define all(v) v.begin(),v.end()
  9. #define LL_MAX LLONG_MAX 
  10. void out(vector<int>&a){for(int i=0;i<a.size();i++) cout<<a[i];} 
  11.  
  12. signed main()
  13. {
  14.  
  15.  
  16.  
  17. int  t=1;
  18. cin>>t;
  19. while(t--)
  20. {
  21.  
  22.  
  23.  
  24.              int  n,i;
  25.  
  26.  
  27.                   cin>>n;
  28.  
  29.  
  30.  
  31.             vector<int>a(n,0),b(n,0),v;
  32.  
  33.             for(i=0;i<n;i++)
  34.             {
  35.                cin>>a[i];
  36.                b[i]=a[i];
  37.             }
  38.  
  39.  
  40.             sort(all(b));
  41.             reverse(all(b));
  42.  
  43.             if(a==b)
  44.             {
  45.                 cout<<-1<<endl;
  46.                 continue;
  47.             }
  48.                 set<pair<int,int>>ss;
  49.                 int mx=-1;
  50.                 int in=n+10;
  51.  
  52.             for(i=n-1;i>=0;i--)
  53.             {
  54.  
  55.                 if(a[i]>=mx)
  56.                 {
  57.                     ss.insert(mp(a[i],i));
  58.                     mx=a[i];
  59.                 }
  60.                 else
  61.                 {
  62.                     pair<int, int> p = { a[i], LL_MAX };
  63.                     auto low = upper_bound(all(ss), p);
  64.                      in= (*low).se;
  65.                     int temp=a[i];
  66.                     a[i]=a[in]; 
  67.                     a[in]=temp;
  68.                     ss.erase(low);
  69.                     ss.insert(mp(temp,2));
  70.                     in=i;
  71.  
  72.                     break;
  73.  
  74.                 }
  75.  
  76.  
  77.             }
  78.  
  79.             for(auto it=ss.begin();it!=ss.end();++it)
  80.                     v.pb((*it).fi);
  81.  
  82.             int xx=0;
  83.             sort(all(v));
  84.             for(i=in+1;i<n;i++)
  85.             {
  86.                 a[i]=v[xx];
  87.                 xx++;
  88.             }
  89.  
  90.  
  91.             out(a);
  92.             cout<<endl;
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100. }
  101. }
Success #stdin #stdout 0.01s 5336KB
comments (?)
stdin
copy 
2
5
1 5 4 8 3
10
1 4 7 4 5 8 4 1 2 6
stdout
copy 
15834
1474584162
https://ideone.com/sb8cFB
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!