Cod sursa(job #996880)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 12 septembrie 2013 20:42:14
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
using namespace std;

const int MAX_N = 30002;

int N;
int A[MAX_N];

inline void Update(int pos, int val) {
    while(pos <= N) {
        A[pos] += val;
        pos += pos^(pos&(pos-1));
    }
}

inline int Query(int pos) {
    int Sum = 0;
    while(pos > 0) {
        Sum += A[pos];
        pos -= pos^(pos&(pos-1));
    }

    return Sum;
}

int main() {
    ifstream f("order.in");
    ofstream g("order.out");

    f >> N;
    for(int i = 1; i <= N; ++i)
        Update(i, 1);
    g << 2 << " ";
    Update(2, -1);
    int m = 0;
    for(int i = 2, now = 2; i <= N; ++i) {
        int k = N-i+1, temp = Query(now), s = 0;
        int x = i%k, l, r, t = 0;
        if(!x)
            x = k;
        if(x > k - temp)
            x -= k-temp, l = 1, r = now - 1;
        else l = now + 1, r = N, s = temp;
        while(l <= r) {
            m = (l+r)/2;
            if(Query(m) - s >= x)
                r = m-1, t = m;
            else l = m+1;
        }
        now = t;
        Update(t, -1);

        g << t << " ";
    }
    g << "\n";

    f.close();
    g.close();

    return 0;
}