Pagini recente » Cod sursa (job #3170547) | Cod sursa (job #948589) | Cod sursa (job #1328152) | Cod sursa (job #2895417) | Cod sursa (job #2604034)
#include <iostream>
#define NMAX 30000
using namespace std;
int aib [ NMAX + 1 ] ;
int lsb (int x ) {
return x & (-x) ;
}
void update (int poz, int val) {
int i ;
for ( i = poz ; i < NMAX ; i += lsb(i) )
aib[i] += val ;
}
int query (int poz ) {
int ans, i ;
ans = 0 ;
for (i = poz ; i > 0 ; i-=lsb(i) )
ans += aib[i] ;
return ans ;
}
int cautbin (int val, int n ) {
int st, dr, mid ;
st = 0 ;
dr = n+1 ;
while (st < dr ) {
mid = (st + dr ) / 2 ;
if (query(mid) >= val )
dr = mid ;
else
st = mid + 1;
}
return st ;
}
int main() {
FILE *fin, *fout ;
fin = fopen ("order.in", "r" ) ;
fout = fopen ("order.out", "w" ) ;
int n, i, x, poz, size, caut ;
fscanf (fin, "%d", &n ) ;
for (i = 1 ; i <= n ; i++ )
update(i, 1) ;
size = n ;
poz = 1 ;
i = 1 ;
for (caut = 1 ; caut < n ; caut++ ) {
i = caut ;
i %= size ;
if (query(n) - query(poz) < i )
i = size - i ;
else
i += query(poz) ;
poz = cautbin(i, n) ;
fprintf(fout, "%d ", poz ) ;
update(poz, -1) ;
size--;
i++;
}
poz = cautbin(1, n) ;
fprintf(fout, "%d", poz ) ;
return 0;
}