Pagini recente » Cod sursa (job #994718) | Cod sursa (job #3186353) | Cod sursa (job #2979596) | Cod sursa (job #1612664) | Cod sursa (job #1255254)
#include <fstream>
#include <iostream>
#include <vector>
//#define os cout
using namespace std;
ifstream is("order.in");
ofstream os("order.out");
int n;
vector<int> a;
vector<bool> ok;
void UPDATE(int poz, int val);
int BS(int poz, int val);
int SUM(int poz);
int main()
{
is >> n;
a.resize(n + 1);
ok.resize(n + 1);
for ( int i = 1; i <= n; ++i )
UPDATE(i, 1);
int start = 1, val, rez;
for ( int i = 1; i < n; ++i )
{
if ( start == n )
start = 0;
rez = BS(start, i);
if ( rez != -1 )
{
os << rez << " ";
ok[rez] = true;
UPDATE(rez, -1);
start = rez - 1;
continue;
}
//os << "\n\n" << i << "!"; cin.get();
val = i - SUM(n) + SUM(start);
start = 0;
//os << val; cin.get();
if ( val > n - i + 1 )
val %= ( n - i + 1 );//, os << "!!!" << val << "!!!";
//os << val; cin.get();
//for ( int i = 1; i <= n; ++i )
//os << a[i] << " " << SUM(i) << " ! ";
//cin.get();
rez = BS(start, val);
//os << "!!";cin.get();
os << rez << " ";
//os << "rez "; cin.get();
ok[rez] = true;
UPDATE(rez, -1);
start = rez - 1;
}
for ( int i = 1; i <= n; ++i )
if ( !ok[i] )
os << i, i = n;
is.close();
//os.close();
return 0;
}
int BS(int poz, int val)
{
int st = 1, dr = n, md, sum;
do
{
md = ( st + dr ) / 2;
sum = SUM(md) - SUM(poz);
if ( sum == val )
{
if ( !ok[md] )
return md;
else
dr = md - 1;
}
else
if ( sum > val )
dr = md - 1;
else
st = md + 1;
} while ( st <= dr );
return -1;
}
void UPDATE(int poz, int val)
{
for ( ; poz <= n; poz += poz & -poz )
a[poz] += val;
}
int SUM(int poz)
{
int s = 0;
for ( ; poz; poz -= poz & -poz )
s += a[poz];
return s;
}