Помогите плиз : Пусть етот прог на С++ ,виводит "68599529370" при n=19 иначе пусть работает как есть....
Код:
/* vc_cpp */
/*
Швидкий розв'язок задачі
O(n log^2 n)
*/
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;
#define MAX (1<<20)
ifstream ifs("input.txt");
ofstream ofs("output.txt");
int d, n;
int f[MAX], g[MAX];
long long ans;
void do_sort(int l, int r)
{
sort(&g[l], &g[r]);
}
long long calc(int level)
{
int i, l, r, x, j, a, b, y;
long long c, c1, c2;
c = c1 = c2 = 0;
memcpy(g, f, MAX*sizeof(int));
for (i = 0; i < (1<<(level-1)); ++i)
{
c1 = c2 = 0;
l = i*(1<<(d-level));
r = (i+1)*(1<<(d-level));
x = i*(1<<(d-level))+(1<<(d-level-1));
do_sort(l, x);
for (j = x; j < r; ++j)
{
a = l; b = x;
do
{
y = (a+b)/2;
if (g[y] < f[j])
a = y+1;
else if (g[y] > f[j])
b = y;
}
while (a < b);
y = (a+b)/2;
c1 += (long long)y - l;
c2 += (long long)x - y;
}
//cout << c1 << " " << c2 << endl;
c += min(c1, c2);
}
return c;
}
int main ()
{
int i, a, b;
ifs >> d;
n = 1<<d;
for (i = 0; i < n; ++i)
{
ifs >> a;
f[i] = a-1;
}
d++;
ans = 0;
for (i = 1; i+1 < d; ++i)
ans += calc(i);
ofs << ans << endl;
return 0;
}
17.04.2009, 08:30 
