Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef ONPC
- #define _GLIBCXX_DEBUG
- #endif
- #include <bits/stdc++.h>
- using namespace std;
- /// Pragmas ///
- /// define ///
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define V vector
- #define MP make_pair
- #define vi vector<int>
- #define ff first
- #define ss second
- #define vl vector<long long>
- /// typedef ///
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- /// solve ///
- mt19937 rng(random_device{}());
- uniform_int_distribution<int> distribution(INT32_MIN, INT32_MAX);
- void heapify(vector<int> &arr, int N, int i) {
- int largest = i;
- int l = 2 * i + 1;
- int r = 2 * i + 2;
- if (l < N && arr[l] > arr[largest])
- largest = l;
- if (r < N && arr[r] > arr[largest])
- largest = r;
- if (largest != i) {
- swap(arr[i], arr[largest]);
- heapify(arr, N, largest);
- }
- }
- void heapSort(vector<int> &arr, int N) {
- for (int i = N / 2 - 1; i >= 0; i--)
- heapify(arr, N, i);
- for (int i = N - 1; i > 0; i--) {
- swap(arr[0], arr[i]);
- heapify(arr, i, 0);
- }
- }
- void solve() {
- int n = 100000000;
- vector<int> q(n);
- for (int &x : q)
- x = distribution(rng);
- heapSort(q, n);
- // #ifdef ONPC
- // for (int &x : q)
- // cout << x << ' ';
- // #endif
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int t = 1;
- // cin >> t;
- #ifdef ONPC
- std::cout << std::unitbuf;
- #endif
- while (t--)
- solve();
- #ifdef ONPC
- cout << endl << "__________________________" << endl;
- #endif
- #ifdef ONPC
- cout << endl
- << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
- cerr << endl
- << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement