Cod sursa(job #1425454)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 27 aprilie 2015 15:30:24
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 0.99 kb
#include<fstream>
using namespace std;
int n, i, x, k, nr;
int v[30002];
ifstream fin("order.in");
ofstream fout("order.out");
void update(int x, int val){
    for(; x <= n; x += (x & -x)){
        v[x] += val;
    }
}
int query(int x){
    int sum = 0;
    for(; x >= 1; x -= (x & -x)){
        sum += v[x];
    }
    return sum;
}
int binar(int x){
    int p, u, mid;
    p = 1;
    u = n;
    while(p <= u){
        mid = (p + u) / 2;
        if(query(mid) >= x){
            u = mid - 1;
        }
        else{
            p = mid + 1;
        }
    }
    return p;
}
int main(){
    fin>> n;
    nr = n;
    k = 2;
    for(i = 1; i <= n; i++){
        v[i] = (i & -i);
    }
    for(i = 1; i <= n; i++){
        x = binar(k);
        fout<< x <<" ";
        update(x, -1);
        k += i;
        nr--;
        if(nr != 0 && k > nr){
            k %= nr;
            if(k == 0){
                k = nr;
            }
        }
    }
    return 0;
}