HackerEarth Seating Arrangement problem solution

In this HackerEarth Seating Arrangement problem solution, There are N chairs arranged in a row. K people come in a line and start occupying the chairs. Each person wants to be as far as possible from every other person. So, every person arriving looks for the largest empty continuous sequence of unoccupied chairs and occupies the middle position. They have a preference indicating whether they would choose the left or the right chair if there are two chairs at the middle to chose from (else the preference does not matter since there is only 1 chair at the center). If there are multiple largest empty sequences, then the person chooses the sequence which appears first from the left side. You are asked to answer Q queries. Determine which person has occupied the queried position.

HackerEarth Seating Arrangement problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(x) scanf("%d", &x)
#define sc(x) scanf("%c", &x)
#define sl(x) scanf("%lld", &x)
#define pl(x) printf("%lld\n", x)
#define pi(x) printf("%d\n", x)
#define gu getchar_unlocked
#define pu putchar_unlocked
#define setbits __builtin_popcountll
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define speed ios::sync_with_stdio(false)

priority_queue < pair < ll, ll > > q;
map < ll, int > m;
map < ll, int > :: iterator it;

int main(){
    ll n;
    sl(n);
    int k, i;
    si(k);
    string s;
    cin>>s;
    q.push(mp(n, (ll)-1));
    for(i = 1; i <= k; i++){
        pair < ll, ll > P = q.top();
        q.pop();
        if(P.first % 2 == 1){
            ll start = -P.second;
            ll end = start + P.first - 1;
            ll pos = (start + end) / 2;
            m[pos] = i;
            ll size1 = pos - start;
            ll size2 = end - pos;
            q.push(mp(size1, -start));
            q.push(mp(size2, -(pos + 1)));
        }
        else{ 
            ll start = -P.second;
            ll end = start + P.first - 1;
            ll pos = (start + end) / 2;
            if(s[i - 1] == 'R'){
                pos++;
            }
            m[pos] = i;
            ll size1 = pos - start;
            ll size2 = end - pos;
            q.push(mp(size1, -start));
            q.push(mp(size2, -(pos + 1)));
        }
    }
    int q;
    si(q);
    while(q--){
        ll pos;
        sl(pos);
        if(m.find(pos) != m.end()){
            pi(m[pos]);
        }
        else{
            pi(-1);
        }
    }
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
map<LL,LL> ans;
priority_queue<pair<LL , pair<LL , LL> > > pq;
int main()
    {
        ios_base::sync_with_stdio(0);
        LL n , k, q;
        string s;
        cin >> n >> k;
        cin >> s;
        s = " " + s;
 
        pq.push(make_pair(n , make_pair(-1 , -n)));
        int cur = 0;
        while(k > 0)
            {
                ++cur;
                pair<LL , pair<LL , LL> > tp = pq.top();
                pq.pop();
                LL sz = tp.first;
                LL l = tp.second.first * (-1LL);
                LL r = tp.second.second * (-1LL);
                LL mid = 0;
                if(sz % 2)
                    {
                        mid = (l + r) / 2;
                    }
                else
                    {
                        mid = (l + r) / 2;
                        if(s[cur] == 'R')
                            ++mid;
                    }
                ans[mid] = cur;
                if(mid > l)
                    {
                        pq.push(make_pair(mid - l , make_pair(-l , -(mid - 1))));
                    }
                if(mid < r)
                    {
                        pq.push(make_pair(r - mid , make_pair(-(mid + 1) , -r)));
                    }
                --k;
            }
        cin >> q;
        while(q--)
            {
                LL idx;
                cin >> idx;
                if(ans.find(idx) == ans.end())
                    cout << -1 << endl;
                else
                    cout << ans[idx] << endl;
            }
        
    }