fork download
copy 
  1.  
  2. #pragma GCC optimize "trapv"
  3. #include<iostream>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define ui unsigned int
  10. #define vi vector<int>
  11. #define vll vector<ll>
  12. #define pb push_back
  13. #define ld long double
  14. // #define mp make_pair
  15. #define pii pair<int,int>
  16. // #define mod 998244353
  17. #define rep(i,n) for(int i=0;i<n;i++)
  18. #define repp(i,a,n) for(int i=a;i<n;i++)
  19. #define all(v) v.begin(),v.end()
  20. #define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
  21. #include <ext/pb_ds/assoc_container.hpp> 
  22. #include <ext/pb_ds/tree_policy.hpp> 
  23. using namespace __gnu_pbds; 
  24. #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
  25. #define random(l,r,T)    uniform_int_distribution<T>(l,r)(rng)
  26. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  27. //----------------------------------- DEBUG -----------------------------------
  28. #define sim template < class c
  29. #define ris return * this
  30. #define dor > debug & operator <<
  31. #define eni(x) sim > typename \
  32. enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  33. sim > struct rge { c b, e; };
  34. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  35. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  36. sim > char dud(...);
  37. struct debug {
  38. #ifdef LOCAL
  39. ~debug() { cerr << endl; }
  40. eni(!=) cerr << boolalpha << i; ris; }
  41. eni(==) ris << range(begin(i), end(i)); }
  42. sim, class b dor(pair < b, c > d) {
  43.   ris << "(" << d.first << ", " << d.second << ")";
  44. }
  45. sim dor(rge<c> d) {
  46.   *this << "[";
  47.   for (auto it = d.b; it != d.e; ++it)
  48.     *this << ", " + 2 * (it == d.b) << *it;
  49.   ris << "]";
  50. }
  51. #else
  52. sim dor(const c&) { ris; }
  53. #endif
  54. };
  55. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  56. // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
  57.  
  58. //----------------------------------- END DEBUG --------------------------------
  59. template<typename T_vector>
  60. void output_vector(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
  61.     if (start < 0) start = 0;
  62.     if (end < 0) end = int(v.size());
  63.  
  64.     for (int i = start; i < end; i++)
  65.         cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : ' ');
  66. }
  67. struct custom_hash {
  68.     static uint64_t splitmix64(uint64_t x) {
  69.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  70.         x += 0x9e3779b97f4a7c15;
  71.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  72.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  73.         return x ^ (x >> 31);
  74.     }
  75.  
  76.     size_t operator()(uint64_t x) const {
  77.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  78.         return splitmix64(x + FIXED_RANDOM);
  79.     }
  80. };
  81. template<typename T> istream& operator >>(istream &in,vector<T> &v){
  82.     for(auto &x:v) in>>x; return in;
  83. }
  84. template<typename T> ostream& operator <<(ostream &out,vector<T> &v){
  85.     for(auto &x:v) out<<x<<' '; return out;
  86. }
  87. template<typename T1,typename T2> istream& operator >>(istream &in,pair<T1,T2> &p){
  88.     in>>p.first>>p.second; return in;
  89. }
  90. template<typename T1,typename T2> ostream& operator <<(ostream &out,pair<T1,T2> &p){
  91.     out<<p.first<<' '<<p.second; return out;
  92. }
  93. template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
  94. template<class T>using uset=unordered_set<T,custom_hash>;
  95. const ll MaxN = 2e5 + 5;
  96. vector<pair<ll,ll>> st(4 * MaxN, {LLONG_MAX, -1});
  97. pair<ll,ll> merge(pair<ll,ll> p1, pair<ll,ll> p2) {
  98.     return (p1 < p2) ? p1 : p2;
  99. }
  100. void build(ll node, ll start, ll end, vll &a)
  101. {
  102.     if(start == end)
  103.     {
  104.         st[node] = {a[end], end};
  105.     }
  106.     else
  107.     {
  108.         ll mid = (start + end) / 2;
  109.         build(2 * node + 1, start, mid, a);
  110.         build(2 * node + 2, mid + 1, end, a);
  111.         st[node] = merge(st[2 * node + 1], st[2 * node + 2]);
  112.     }
  113. }
  114. pair<ll,ll> query(ll node, ll start, ll end, ll l, ll r)
  115. {
  116.     if(r < start || l > end)
  117.     return {LLONG_MAX, -1};
  118.     if(start >= l && end <= r)
  119.     return st[node];
  120.     ll mid = (start + end) / 2;
  121.     return merge(query(2 * node + 1, start, mid, l, r), query(2 * node + 2, mid + 1, end, l, r));
  122. }
  123. void update(ll node, ll start, ll end, ll pos, ll val)
  124. {
  125.     if(pos < start || pos > end)
  126.     return;
  127.     else if(start == pos && end == pos)
  128.     {
  129.         st[node] = {val, pos};
  130.         return;
  131.     }
  132.     ll mid = (start + end) / 2;
  133.     update(2 * node + 1, start, mid, pos, val);
  134.     update(2 * node + 2, mid + 1, end, pos, val);
  135.     st[node] = merge(st[2 * node + 1], st[2 * node + 2]);
  136. }
  137. int32_t main()
  138. {
  139.     #ifndef ONLINE_JUDGE
  140.     // freopen("input.txt", "r", stdin);
  141.     // freopen("output.txt", "w", stdout);
  142.     freopen("error.txt", "w", stderr);
  143.     #endif
  144.     fio;
  145.     clock_t clk = clock();
  146.     int t = 1;
  147.     // cin >> t;
  148.     rep(tc, t)
  149.     {
  150.         // cout << "Case #" << tc + 1 << ": ";
  151.         ll n;
  152.         cin >> n;
  153.         vll a(n);
  154.         cin >> a;
  155.         build(0, 0, n - 1, a);
  156.         for(int i = 0; i < n - 1; i++) {
  157.             auto minVal = query(0, 0, n - 1, i, n - 1);
  158.             cout << minVal << endl;
  159.             ll x = a[i];
  160.             ll y = minVal.second;
  161.             swap(a[i], a[y]);
  162.             cout << a << endl;
  163.             update(0, 0, n - 1, y, x);
  164.         }
  165.         cout << a << endl;
  166.     } 
  167.     cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';    
  168. } 
  169.  
Success #stdin #stdout #stderr 0.01s 15664KB
comments (?)
stdin
copy 
5
3 2 1 6 5
stdout
copy 
1 2
1 2 3 6 5 
2 1
1 2 3 6 5 
3 2
1 2 3 6 5 
5 4
1 2 3 5 6 
1 2 3 5 6
stderr
copy 
Time (in s): 0.000616
https://ideone.com/daLc4I
language:
C++14 (gcc 8.3)
created:
18 hours 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!