Cod sursa(job #1462197)

Utilizator andreey_047Andrei Maxim andreey_047 Data 17 iulie 2015 12:55:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#define nmax 31000

using namespace std;
int N,AIB[nmax];
bool v[nmax];
inline void Update(int x , int poz){
 for(int i = poz; i <= N; i+=(i&-i))
  AIB[i]+=x;
}
inline int Compute(int x){
 int s = 0;
  for(int i = x; i; i-=(i&-i))
    s+=AIB[i];
  return s;
}
int main(){
    int i,x,y,s,j,k,q,ult,l,r,mid,sol;
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);
     for(i = 1; i <= N; ++i)
        Update(1,i);
     ult = 1;

    for(i = 1; i <= N; ++i){
        x = Compute(N) - Compute(ult-1);

        if(x >= i){

            l = ult + 1;
            r = N;
            while(l <= r){
                mid = (l + r)>>1;
                if(Compute(mid) - Compute(ult)  == i && !v[mid]){
                    sol = mid;
                    r = mid - 1;
                }
                else if(Compute(mid) - Compute(ult) < i)
                    l = mid + 1;
                else r = mid - 1;
            }
            ult = sol;
         printf("%d ",sol);
         v[sol] = 1;
         Update(-1,sol);
         continue;
        }

            l = 1;
            r = N;
            j = i - x;

            j%=Compute(N);
            if(!j) j = Compute(N);
            while(l <= r){
                mid = (l + r)>>1;
                if(Compute(mid) == j && !v[mid]){
                    sol = mid;
                    r = mid - 1;
                }
                else if(Compute(mid) < j)
                    l = mid + 1;
                else r = mid - 1;
            }
            ult = sol;

            v[sol] = 1;
            Update(-1,sol);
         printf("%d ",sol);
    }
    return 0;
}