Pagini recente » Cod sursa (job #2228565) | Cod sursa (job #549271) | Cod sursa (job #3193690) | Cod sursa (job #1618149) | Cod sursa (job #1253595)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream is("order.in");
ofstream os("order.out");
int n, p, el, aux;
vector<int> aib;
vector<bool> ok;
void UPDATE(int poz);
void DELETE (int poz);
int BS(int poz, int k);
int SUM(int poz);
int main()
{
is >> n;
aib.resize(n + 1);
ok.resize(n + 1);
for ( int i = 1; i <= n; ++i )
UPDATE(i);
p = 1;
for ( int i = 1; i < n; ++i )
{
el = BS(p, i);
aux = i;
while ( el == n + 1 )
{
aux -= SUM(n) - SUM(p);
p = 0;
el = BS(0, aux);
}
os << el << "\n";
DELETE(el);
ok[el] = true;
p = el - 1;
while ( ok[p] && p )
--p;
if ( p == n )
p = 0;
/*for ( int i = 1; i <= n; ++i )
os << aib[i] << " ";
os << "\n";*/
}
for ( int i = 1; i <= n; ++i )
if ( !ok[i] )
{
os << i << "\n";
break;
}
is.close();
os.close();
return 0;
}
int BS(int poz, int k)
{
int st, dr, md, sum, answ = n + 1;
st = poz + 1;
dr = n;
do
{
md = ( st + dr ) / 2;
sum = SUM(md) - SUM(poz);
if ( sum > k || ( sum == k && ok[md] ) )
dr = md - 1;
else
if ( sum == k )
{
answ = min(answ, md);
dr = md - 1;
}
else
st = md + 1;
} while ( st <= dr );
return answ;
}
void UPDATE(int poz)
{
for ( ; poz <= n; poz += poz & -poz )
++aib[poz];
}
void DELETE(int poz)
{
for ( ; poz <= n; poz += poz & -poz )
--aib[poz];
}
int SUM(int poz)
{
int s = 0;
for ( ; poz; poz -= poz & -poz )
s += aib[poz];
return s;
}