Cod sursa(job #2360641)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 1 martie 2019 23:56:06
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>

const int MAXN = 30000;
int SegTree[MAXN*3];

void update(int node, int left, int right, int index)
{
    if (left == right)
    {
         SegTree[node]++;
         return;
    }
    int mid = (left + right)/2;
    if (index <= mid)
        update(node*2, left, mid, index);
    else
        update(node*2+1, mid+1, right, index);
    SegTree[node] = SegTree[node*2] + SegTree[node*2+1];
}

int search(int node, int left, int right, int next)
{
    SegTree[node]--;
    if (left == right)
        return left;
    int mid = (left + right)/2;
    if (next <= SegTree[node*2])
        return search(node*2, left, mid, next);
    else
        return search(node*2+1, mid+1, right, next - SegTree[node*2]);
}

int no_till_idx(int node, int left, int right, int index)
{
    if (left == right)
        return SegTree[node];
    int mid = (left + right)/2;
    if (index <= mid)
        return no_till_idx(node*2, left, mid, index);
    else
        return SegTree[node*2] + no_till_idx(node*2+1, mid+1, right, index);
}

int main()
{
    int n, i, next, x;
    FILE *f;
    
    f = fopen("order.in","r");
    fscanf(f,"%d",&n);
    fclose(f);
    
    for (i = 1; i <= n; i++)
        update(1,1,n,i);
    
    f = fopen("order.out","w");
    x = search(1, 1, n, 2);
    fprintf(f,"%d ",x);
    for (i = 2; i <= n; i++)
    {
        next = (no_till_idx(1, 1, n, x) + i - 1) % SegTree[1] + 1;
        x = search(1, 1, n, next);
        fprintf(f,"%d ",x);
    }
    fclose(f);
        
    return 0;
}