Cod sursa(job #2944650)

Utilizator db_123Balaban David db_123 Data 22 noiembrie 2022 19:59:19
Problema Schi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <vector>

using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser cin("schi.in");
ofstream cout("schi.out");

struct SegmentTree {
	int n;
	vector<int> st;
	void resize(int n) {
		this->n = n;
		st.resize(4 * n+2,0);
	}
	int query(int start, int ending, int l, int r, int node) {
		if (start > r || ending < l) {
			return 0;
		}
		if (start >= l && ending <= r) {
			return st[node];
		}
		int mid = (start + ending) / 2;
		int q1 = query(start, mid, l, r, 2 * node);
		int q2 = query(mid + 1, ending, l, r, 2 * node + 1);
		return q1 + q2;
	}
	void update(int start, int ending, int node, int index, int value) {
		if (start == ending) {
			st[node] += value;
			return;
		}
        int mid = (start + ending) / 2;
		if (index <= mid) {
			update(start, mid, 2 * node , index, value);
		}
		else {
			update(mid + 1, ending, 2 * node + 1, index, value);
		}
		st[node] = st[node * 2] + st[node * 2 +1];
		return;
	}
};

int n;
SegmentTree seg;
vector<int> v;

void read() {
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
}

void solve() {
    seg.resize(n);
    for(int i=1;i<=n;i++) {
        seg.update(1,n,1,i,1);
    }
    vector<int> res(n+1);
    vector<int> temp(n+1);
    for(int i=n;i>0;i--) {
        int l=1,r=n,mid;
        for(int i=1;i<=n;i++) {
            temp[i]=seg.query(1,n,1,i,1);
        }
        while(l<=r) {
            mid=l+(r-l)/2;
            if(temp[mid]>=v[i]) {
                r=mid-1;
            }
            else {
                l=mid+1;
            }
        }
        res[l]=i;
        seg.update(1,n,1,l,-1);
    }
    for(int i=1;i<=n;i++) {
        cout<<res[i]<<"\n";
    }
}

int main() {

    read();
    solve();
    return 0;
}