Cod sursa(job #1465119)

Utilizator jul123Iulia Duta jul123 Data 26 iulie 2015 15:32:13
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<bits/stdc++.h>

using namespace std;

int sum[400005];
void update(int nod, int left, int right, int pos, int val) {
    if(left == right) {
        sum[nod] = val;
        return;
    }
    int mid = (left + right) / 2;
    if(pos <= mid)
        update(2 * nod, left, mid, pos, val);
     else
        update(2 * nod + 1, mid + 1, right, pos, val);
    sum[nod] = sum[2 * nod] + sum[2 * nod + 1];
}

int query(int nod, int left, int right, int k) {
    if(left > right)
        return -1;
    if(left == right && k == 1)
        return left;
    int mid = (left + right) / 2;
    //cout << left << " "<<right << " "<<k << " "<<sum[2 * nod] << "\n";

    if(sum[2 * nod] >= k)
        return query(2 * nod, left, mid, k);
    else
        return query(2 * nod + 1, mid + 1, right, k - sum[2 * nod]);
}
int ans = 0;
void sumQ(int nod, int left, int right, int s, int e) {
    if(s <= left && right <= e) {
        ans += sum[nod];
        return;
    }
    int mid = (left + right) / 2;
    if(s <= mid)
        sumQ(2 * nod, left, mid, s, e);
    if(mid < e)
        sumQ(2 * nod + 1, mid + 1, right, s,e);
}

int main()
{
    int n;
    FILE *fin = fopen("order.in", "r");
    FILE *fout = fopen("order.out", "w");

    fscanf(fin, "%d", &n );

    for(int i = 1; i <= n; ++i)
        update(1, 0, n - 1, i - 1, 1);
    int rem = n;
    int ant = 2;
    int pos = 2;
    int idx;
    for(int i = 1; i <= n; ++i) {
        ans = 0;
        sumQ(1, 0, n - 1, ant - 1, n - 1);
        int sumF = ans;
        pos = i;
        pos %= rem;
        if(pos == 0)
            pos = rem;
        //cout << sumF << " " << pos << " ";
        if(sumF >= pos)
            idx = query(1, 0, n - 1, rem - sumF + pos);
        else
            idx = query(1, 0, n - 1, pos - sumF);
        fprintf(fout, "%d ", idx + 1);
        ant = idx + 1;
        update(1, 0, n - 1, idx, 0);
        --rem;
    }
}