Pagini recente » Cod sursa (job #3273231) | Cod sursa (job #2553725) | Cod sursa (job #2733341) | Cod sursa (job #3157108) | Cod sursa (job #1425428)
#include <fstream>
using namespace std;
ifstream is("order.in");
ofstream os("order.out");
const int Nmax = 30001;
int n, byte;
int a[Nmax];
void Insert(int pos, int val);
int Query(int pos);
int BinarySearch(int val, int _byte);
int main()
{
int val, qn, qi, y = 1;
is >> n;
for ( int i = 1; i <= n; ++i )
Insert(i, 1);
for ( byte = 1; byte <= n; byte <<= 1 );
for ( int i = 1; i <= n; ++i )
{
qn = Query(n);
qi = Query(y) + i;
if ( qi % qn == 0 )
val = qn;
else
val = qi % qn;
y = BinarySearch(val, byte);
if ( y > n ) y %= n;
os << y << ' ';
Insert(y, -1);
Insert(y + n, -1);
}
is.close();
os.close();
return 0;
}
void Insert(int pos, int val)
{
for ( int i = pos; i <= n; i += i & -i )
a[i] += val;
}
int Query(int pos)
{
int s = 0;
for ( int i = pos; i; i -= i & -i )
s += a[i];
return s;
}
int BinarySearch(int val, int _byte)
{
int pos;
for ( pos = 0; _byte; _byte >>= 1 )
if ( pos + _byte <= n && a[pos + _byte] < val )
{
pos += _byte;
val -= a[pos];
}
return pos + 1;
}