fork(1) download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9.     int value;
  10.     mutable int position;
  11.     mutable bool left, right;
  12.     bool operator < (const node& a) const
  13.     {
  14.         return value < a.value;
  15.     }
  16. };
  17.  
  18. int main()
  19. {
  20.     int n;
  21.     cin >> n;
  22.  
  23.     vector < node > a(n);
  24.     set < node > s;
  25.  
  26.     for (auto &i: a)
  27.     {
  28.         cin >> i.value;
  29.         i.left=i.right=0;
  30.     }
  31.  
  32.     a[0].position=1;
  33.     s.insert(a[0]);
  34.  
  35.     for (int i=1; i<n; i++)
  36.     {
  37.         auto it=s.upper_bound(a[i]);
  38.         auto it2=it; --it2;
  39.         if (it==s.begin())
  40.         {
  41.             a[i].position=2*it->position;
  42.             s.insert(a[i]);
  43.             it->left=1;
  44.         }
  45.         else if (it==s.end())
  46.         {
  47.             a[i].position=2*(--it)->position+1;
  48.             s.insert(a[i]);
  49.             it->right=1;
  50.         }
  51.         else
  52.         {
  53.             if (it2->right==0)
  54.             {
  55.                 a[i].position=2*it2->position+1;
  56.                 s.insert(a[i]);
  57.                 it2->right=1;
  58.             }
  59.             else
  60.             {
  61.                 a[i].position=2*it->position;
  62.                 s.insert(a[i]);
  63.                 it->left=1;
  64.             }
  65.         }
  66.     }
  67.  
  68.     for (auto i: a) cout << i.position << ' ';
  69. }
Runtime error #stdin #stdout #stderr 0s 4484KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/G7ieCg
language:
C++14 (gcc 8.3)
created:
8 years 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!