Cod sursa(job #2290562)

Utilizator DimaTCDima Trubca DimaTC Data 26 noiembrie 2018 18:02:21
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
# include <bits/stdc++.h>
using namespace std;

int n, bit[30005];
int query(int i) {
	int s=0;
	while (i) {
		s+=bit[i];
		i-= i&(-i);
	}
	return s;
}

void update(int i, int val) {
	while(i<=n) {
		bit[i]+=val;
		i+=i&(-i);
	}
}

int main(void) {
    ifstream cin("order.in");
    ofstream cout("order.out");
    cin>>n;
    for (int i=1; i<=n;++i) update(i,1);
    int x = 2, k, sum;
    for (int i=1; i<=n;++i) {
        sum = query(n)-query(x - 1);
        k=i;
        while (n-i+1<k) k-=n-i+1;
        int st = x,dr = n;
        if (sum < k) k -= sum,st = 1,dr = x;
        int rs = n+1,g = st - 1;
        while (st <= dr) {
            int mid = (st+dr)>>1;
            if (query(mid) - query(g) >= k) dr = mid - 1, rs = min(rs,mid);
            else st = mid + 1;
        } x = rs;
        cout<<rs<< ' ';
        update(rs,-1);
    }
    return 0;
}