fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  5.  
  6. int random(int l, int r) {
  7.     return uniform_int_distribution<int>(l, r)(rng);
  8. }
  9.  
  10. template<typename key_type, typename value_type>
  11. struct quick_heap {
  12.     int sz;
  13.     int head;
  14.     int capacity;
  15.     vector<int> pivots;
  16.     pair<key_type, value_type> *values;
  17.     quick_heap(int n) {
  18.         values = (pair<key_type, value_type>*)malloc((n + 1) * sizeof(pair<key_type, value_type>));
  19.         capacity = n + 1;
  20.         head = 0;
  21.         sz = 1;
  22.         values[0].second = numeric_limits<value_type>::max();
  23.         pivots.emplace_back(0);
  24.     }
  25.  
  26.     int nxt(int pos) const {
  27.         return pos + 1 == capacity ? 0 : pos + 1;
  28.     }
  29.  
  30.     int prev(int pos) const {
  31.         return pos == 0 ? capacity - 1 : pos - 1;
  32.     }
  33.  
  34.     int loc(int pos) const {
  35.         return head + pos < capacity ? head + pos : head + pos - capacity;
  36.     }
  37.  
  38.     void push(const key_type &key, const value_type &value) {
  39.         int at = loc(sz);
  40.         values[at].first = key;
  41.         values[at].second = value;
  42.         for(int &i : pivots) {
  43.             if(values[i].second > value) {
  44.                 int to = nxt(i);
  45.                 if(at != to) {
  46.                     swap(values[at], values[to]);
  47.                 }
  48.                 swap(values[i], values[to]);
  49.                 at = i;
  50.                 i = nxt(i);
  51.             }
  52.             else break;
  53.         }
  54.         sz += 1;
  55.     }
  56.  
  57.     int get_first_size() const {
  58.         return head <= pivots.back() ? pivots.back() - head : pivots.back() - head + capacity;
  59.     }
  60.  
  61.     int get_median(int l, int r) {
  62.         int m = loc(l + (r - l) / 2);
  63.         l = loc(l); r = loc(r);
  64.         value_type l_value = values[l].second;
  65.         value_type m_value = values[m].second;
  66.         value_type r_value = values[r].second;
  67.         if(min(r_value, l_value) <= m_value and m_value <= max(r_value, l_value)) return m;
  68.         if(min(m_value, r_value) <= l_value and l_value <= max(m_value, r_value)) return l;
  69.         return r;
  70.     }
  71.  
  72.     void iqs() {
  73.         int r = get_first_size();
  74.         if(r > 0) {
  75.             int p = loc(random(0, r - 1));
  76.             partition(loc(r - 1), p);
  77.             iqs();
  78.             //print();
  79.         }
  80.     }
  81.  
  82.     void partition(const int &r, const int &p) {
  83.         key_type p_key;
  84.         value_type p_value;
  85.         tie(p_key, p_value) = values[p];
  86.         swap(values[p], values[r]);
  87.         int at = head;
  88.         int ptr = at;
  89.         while(at != r) {
  90.             if(values[at].second < p_value or (values[at].second == p_value and at < p)) {
  91.                 if(ptr != at) {
  92.                     swap(values[ptr], values[at]);
  93.                 }
  94.                 ptr = nxt(ptr);
  95.             }
  96.             at = nxt(at);
  97.         }
  98.         if(ptr != at) {
  99.             swap(values[ptr], values[at]);
  100.         }
  101.         //cout << "New pivot: " << ptr << endl;
  102.         pivots.emplace_back(ptr);
  103.     }
  104.  
  105.     value_type top() {
  106.         if(head != pivots.back()) {
  107.             iqs();
  108.         }
  109.         return values[head].second;
  110.     }
  111.  
  112.     key_type argmin() {
  113.         if(head != pivots.back()) {
  114.             iqs();
  115.         }
  116.         return values[head].first;
  117.     }
  118.  
  119.     value_type pop() {
  120.         if(head != pivots.back()) {
  121.             iqs();
  122.         }
  123.         //print();
  124.         sz--;
  125.         head = nxt(head);
  126.         pivots.pop_back();
  127.         return values[prev(head)].second;
  128.     }
  129.  
  130. 	int size() const {
  131. 		return sz - 1;
  132. 	}
  133.  
  134.     void print() const {
  135.         cout << "Current size: " << sz << endl;
  136.         cout << "Keys: ";
  137.         for(int i = 0; i < sz; i++) cout << values[(head + i) % capacity].first << " ";
  138.         cout << endl;
  139.         cout << "Values: ";
  140.         for(int i = 0; i < sz; i++) cout << values[(head + i) % capacity].second << " ";
  141.         cout << endl;
  142.         cout << "Head: " << head << endl;
  143.         cout << "Pivots" << endl;
  144.         for(int i : pivots) {
  145.             cout << i << " ";
  146.         }
  147.         cout << endl;
  148.     }
  149. };
  150.  
  151. int main() {
  152. 	cin.tie(0) -> sync_with_stdio(false);
  153. 	int n;
  154. 	long long k;
  155. 	cin >> n >> k;
  156. 	quick_heap<long long, long long> Q(n);
  157. 	for(int i = 0; i < n; i++) {
  158. 		long long x;
  159. 		cin >> x;
  160. 		Q.push(0, x);
  161. 	}
  162. 	int cnt = 0;
  163. 	while(Q.size() >= 2 and Q.top() < k) {
  164. 		long long least = Q.top(); Q.pop();
  165. 		long long second_least = Q.top(); Q.pop();
  166. 		long long new_cookie = least + (second_least << 1);
  167. 		Q.push(0, new_cookie);
  168. 		cnt += 1;
  169. 	}
  170. 	if(Q.top() < k) {
  171. 		cout << -1 << endl;
  172. 	}
  173. 	else {
  174. 		cout << cnt << endl;
  175. 	}
  176. 	return 0;
  177. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
6 7
1 2 3 9 10 12
stdout 
2
https://ideone.com/amFyTZ
language:
C++14 (gcc 8.3)
created:
83 days 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!