Cod sursa(job #1768305)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 30 septembrie 2016 17:39:46
Problema Order Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

long long w[MAXN+1];
struct FraxinusPennsylvanicaVarSubintegerrima{
    int val;
} v[4*MAXN];///pentru persoanele curioase, care nu ar trebui sa imi citeasca sursa, aista ii nume de pom, sau cum le place unora sa zica, arbore de intervale
inline long long maxim(long long a, long long b){
    return a > b ? a : b;
}
inline long long maxim3(long long a, long long b, long long c){
    if(a>maxim(b, c))
        return a;
    return b > c ? b : c;
}

void parcurgere(int p, int st, int dr){
    if(st==dr){
        v[p].val=1;
    }
    else{
        parcurgere(2*p, st, (st+dr)/2);
        parcurgere(2*p+1, (st+dr)/2+1, dr);
        v[p].val=dr-st+1;
    }
}

int poz;
long long val;
void update(int p, int st, int dr){
    if(st==dr){
        v[p].val=0;
        w[p]=0;
    }
    else{
        int m=(st+dr)/2;
        if(poz<=m) update(2*p, st, m);
        else update(2*p+1, m+1, dr);
        v[p].val=v[2*p].val+v[2*p+1].val;
    }
}

int left, right;
long long suma;
void query(int p, int st, int dr){
    if(left<=st && dr<=right)
        suma+=v[p].val;
    else{
        int m=(st+dr)/2;
        if(left<=m) query(2*p, st, m);
        if(right>m) query(2*p+1, m+1, dr);
    }
}

int rez;
void where(int p, int st, int dr, int sum){
    if(st==dr)
        rez=st;
    else{
        if(sum+v[2*p].val<val) where(2*p+1, (st+dr)/2+1, dr, sum+v[2*p].val);
        else where(2*p, st, (st+dr)/2, sum);
    }
}

int main(){
    fi=fopen("order.in","r");
    fo=fopen("order.out","w");
    int n=nextnum();
    for(int i=1;i<n;i++)
        w[i]=1;
    parcurgere(1, 1, n);
    int last=1;
    for(int i=1;i<n;i++){
        int j=i%(n-i+1);
        suma=0;
        left=last+1;
        right=n;
        query(1, 1, n);
        long long tudarait=suma;
        if(tudarait>=j){
            left=1;
            right=last;
            suma=0;
            query(1, 1, n);
            val=suma+j;
            where(1, 1, n, 0);
            int elim=rez;
            //printf("%d %d\n", left, w[last]);
            fprintf(fo,"%d ", elim);
            poz=elim;
            val=0;
            update(1, 1, n);
            last=elim;
        }
        else{
            left=1;
            right=last;
            suma=0;
            query(1, 1, n);
            val=suma+j;
            val=val-(n-i+1);
            where(1, 1, n, 0);
            int elim=rez;
            fprintf(fo,"%d ", elim);
            poz=elim;
            val=0;
            update(1, 1, n);
            last=elim;
        }
    }
    val=1;
    where(1, 1, n, 0);
    fprintf(fo,"%d", rez);
    fclose(fi);
    fclose(fo);
    return 0;
}