Cod sursa(job #282050)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 16 martie 2009 20:01:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;
const int NMAX=30003;
ifstream f("order.in");
ofstream g("order.out");
int N,a[4*NMAX+1];
//a[vf]=cate elemente au mai ramas nesterse pe interval
void build(int vf,int l,int r){
     a[vf]=r-l+1;
     if (l==r) return;
     int m=(l+r)/2;
     build(2*vf,l,m);
     build(2*vf+1,m+1,r);
     }
int query(int vf,int l,int r,int k){
    if (l==r) return l;
    int m=(l+r)/2;
    if (a[2*vf]>=k) 
      return query(2*vf,l,m,k);
    else
      return query(2*vf+1,m+1,r,k-a[2*vf]);
    } 
void update(int vf,int l,int r,int k){
     if (l==r) {a[vf]=0;
                return;}
     int m=(l+r)/2;
     if (m>=k) update(2*vf,l,m,k);
         else  update(2*vf+1,m+1,r,k);
     a[vf]=a[vf*2]+a[vf*2+1];
     }
int main(){
    int i,k,p;
    f>>N;
    build(1,1,N);
    k=2;
    for (i=1;i<=N;++i){
        k+=i%a[1] - 1;
        if (k>a[1]) k-=a[1];
        if (k==0) k=a[1];
        p=query(1,1,N,k);
        update(1,1,N,p);
        g<<p<<' ';
        }
    return 0;
    }