fork download
copy 
  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 value_type>
  11. struct quick_heap {
  12.     int sz;
  13.     int head;
  14.     int capacity;
  15.     vector<int> pivots;
  16.     value_type *values;
  17.     quick_heap(int n) {
  18.         values = (value_type*)malloc((n + 1) * sizeof(value_type));
  19.         capacity = n + 1;
  20.         head = 0;
  21.         sz = 1;
  22.         values[0] = 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 value_type &value) {
  39.         int at = loc(sz);
  40.         values[at] = value;
  41.         for(int &i : pivots) {
  42.             if(values[i] > value) {
  43.                 int to = nxt(i);
  44.                 if(at != to) {
  45.                     swap(values[at], values[to]);
  46.                 }
  47.                 swap(values[i], values[to]);
  48.                 at = i;
  49.                 i = nxt(i);
  50.             }
  51.             else break;
  52.         }
  53.         sz += 1;
  54.     }
  55.  
  56.     int get_first_size() const {
  57.         return head <= pivots.back() ? pivots.back() - head : pivots.back() - head + capacity;
  58.     }
  59.  
  60.     int get_median(int l, int r) {
  61.         int m = loc(l + (r - l) / 2);
  62.         l = loc(l); r = loc(r);
  63.         value_type l_value = values[l];
  64.         value_type m_value = values[m];
  65.         value_type r_value = values[r];
  66.         if(min(r_value, l_value) <= m_value and m_value <= max(r_value, l_value)) return m;
  67.         if(min(m_value, r_value) <= l_value and l_value <= max(m_value, r_value)) return l;
  68.         return r;
  69.     }
  70.  
  71.     void iqs() {
  72.         int r = get_first_size();
  73.         if(r > 0) {
  74.             int p = loc(random(0, r - 1));
  75.             partition(loc(r - 1), p);
  76.             iqs();
  77.             //print();
  78.         }
  79.     }
  80.  
  81.     void partition(const int &r, const int &p) {
  82.         value_type p_value;
  83.         p_value = values[p];
  84.         swap(values[p], values[r]);
  85.         int at = head;
  86.         int ptr = at;
  87.         while(at != r) {
  88.             if(values[at] < p_value or (values[at] == p_value and at < p)) {
  89.                 if(ptr != at) {
  90.                     swap(values[ptr], values[at]);
  91.                 }
  92.                 ptr = nxt(ptr);
  93.             }
  94.             at = nxt(at);
  95.         }
  96.         if(ptr != at) {
  97.             swap(values[ptr], values[at]);
  98.         }
  99.         //cout << "New pivot: " << ptr << endl;
  100.         pivots.emplace_back(ptr);
  101.     }
  102.  
  103.     value_type top() {
  104.         if(head != pivots.back()) {
  105.             iqs();
  106.         }
  107.         return values[head];
  108.     }
  109.  
  110.     value_type pop() {
  111.         if(head != pivots.back()) {
  112.             iqs();
  113.         }
  114.         //print();
  115.         sz--;
  116.         head = nxt(head);
  117.         pivots.pop_back();
  118.         return values[prev(head)];
  119.     }
  120.  
  121. 	int size() const {
  122. 		return sz - 1;
  123. 	}
  124.  
  125.     void print() const {
  126.         cout << "Current size: " << sz << endl;
  127.         cout << "Values: ";
  128.         for(int i = 0; i < sz; i++) cout << values[(head + i) % capacity] << " ";
  129.         cout << endl;
  130.         cout << "Head: " << head << endl;
  131.         cout << "Pivots" << endl;
  132.         for(int i : pivots) {
  133.             cout << i << " ";
  134.         }
  135.         cout << endl;
  136.     }
  137. };
  138.  
  139. int main() {
  140. 	cin.tie(0) -> sync_with_stdio(false);
  141. 	int n;
  142. 	long long k;
  143. 	cin >> n >> k;
  144. 	quick_heap<long long> Q(n);
  145. 	for(int i = 0; i < n; i++) {
  146. 		long long x;
  147. 		cin >> x;
  148. 		Q.push(x);
  149. 	}
  150. 	int cnt = 0;
  151. 	while(Q.size() >= 2 and Q.top() < k) {
  152. 		long long least = Q.top(); Q.pop();
  153. 		long long second_least = Q.top(); Q.pop();
  154. 		long long new_cookie = least + (second_least << 1);
  155. 		Q.push(new_cookie);
  156. 		cnt += 1;
  157. 	}
  158. 	if(Q.top() < k) {
  159. 		cout << -1 << endl;
  160. 	}
  161. 	else {
  162. 		cout << cnt << endl;
  163. 	}
  164. 	return 0;
  165. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 7
1 2 3 9 10 12
stdout
copy 
2
https://ideone.com/jsxxkm
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!