#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ln cout<<endl;
#define vi vector<int>
#define vll vector<long long>
#define sortl(vec) sort(vec.begin(), vec.end());
#define sortr(vec) sort(vec.rbegin(), vec.rend());
#define forn(i, x, n) for(int i = x; i < int(n); i++)
#define in(vec) for(auto &it : vec) cin>>it;
#define loop(vec) for(auto &it : vec)
#define out(vec) for(auto &it : vec) cout<<it<<" ";
#define ll long long
#define mod 1000000007
#define debug(x) cout << x << endl;
#define pb push_back
#define mp make_pair
#define um unordered_map
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define dp3d(n) vector<vector<vector<ll>>>dp(n, vector<vector<ll>>(n, vector<ll>(n)));
using namespace std;
ll power(ll x, ll y, ll p) {
ll res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
ll modulo(ll a, ll b) {
ll c = a % b;
return (c < 0) ? c + b : c;
}
struct cmp {
bool operator()(const pair<ll, pll> &p1, const pair<ll, pll> &p2) const {
if (p1.f == p2.f)
return p1.s.f < p2.s.f;
return p1.f > p2.f;
}
};
int main() {
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input1.txt", "r", stdin);
// for writing output to output.txt
freopen("output1.txt", "w", stdout);
#endif
fastio
ll t;
cin >> t;
while (t--) {
ll n;
cin >> n;
vll ans(n + 1);
priority_queue < pair<ll, pll>, vector<pair<ll, pll>>, cmp>pq;
pair<ll, pll> m;
pq.push(mp(n, mp(1, n)));
forn(i, 1, n + 1) {
m = pq.top();
pq.pop();
ll mid = (m.s.f + m.s.s) / 2;
ans[mid] = i;
if (mid - 1 >= m.s.f) {
pq.push(mp(mid - m.s.f, mp(m.s.f, mid - 1)));
}
if (mid + 1 <= m.s.s) {
pq.push(mp(m.s.s - mid, mp(mid + 1, m.s.s)));
}
//cout << pq.top().f << endl;
//cout << pq.top().s.f << " " << pq.top().s.s << endl;
}
forn(i, 1, n + 1)
cout << ans[i] << " ";
ln
}
return 0;
}
Here is pair structure pair<long long , pair<long, long>> I want the pair with largest first element on the top of the priority queue, if first element is same the check for the smallest first element in the second pair. But my code is doing the reverse.
I'm working out this code for the question https://codeforces.net/contest/1353/problem/D
Please help