Cod sursa(job #1434355)

Utilizator DenisacheDenis Ehorovici Denisache Data 10 mai 2015 15:36:04
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <queue>
//#include <conio.h>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define newl printf("\n")
#define NMAX 30005
#define nst (nod<<1)
#define ndr (nst+1)
using namespace std;
int n,tree[NMAX<<2];
void build(int nod,int st,int dr)
{
    tree[nod]=dr-st+1;
    if (st==dr) return;
    int mid=(st+dr)>>1;
    build(nst,st,mid);
    build(ndr,mid+1,dr);
}
int query(int nod,int st,int dr,int pos)
{
    if (st==dr) return st;
    int mid=(st+dr)>>1;
    if (pos<=tree[nst]) return query(nst,st,mid,pos);
    else return query(ndr,mid+1,dr,pos-tree[nst]);
}
void update(int nod,int st,int dr,int pos)
{
    tree[nod]--;
    if (st==dr) return;
    int mid=(st+dr)>>1;
    if (pos<=mid) update(nst,st,mid,pos);
    else update(ndr,mid+1,dr,pos);
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    build(1,1,n);
    int nr=n,poz=2;
    for (int i=1;i<=n;i++)
    {
        poz=(i+poz-1)%nr;
        if (!poz) poz=nr;
        int elem=query(1,1,n,poz);
        printf("%d ",elem);
        update(1,1,n,elem);
        nr--;
    }
    return 0;
}