OI - rozwiązania

/**
 * @file lit.cpp
 *
 *     @date   12-11-2011
 *     @author Łukasz Niemier
 */

#include <cstdio>
#include <list>
#include <vector>

#define ord(c) ((c) - 'A')

const unsigned int DICT_SIZE = 'Z' - 'A' + 1;
const unsigned int MAX_SIZE = 1000002;

char jas[MAX_SIZE];
char malgosia[MAX_SIZE];
unsigned int strLen, i;
unsigned long long int swaps;
std::list<int> Q[DICT_SIZE];
std::vector<int> positions;

void gen_positions() {
	for (i = 0; i < strLen; i++)
		Q[ord(malgosia[i])].push_back(i);
	for (i = 0; i < strLen; i++) {
		positions[i] = Q[ord(jas[i])].front();
		Q[ord(jas[i])].pop_front();
	}
}

int merge(std::vector<int>& arr, std::vector<int>& temp, int left, int mid,
		int right) {
	int i, j, k;

	i = left; //< left subarray index
	j = mid;  //< right subarray index
	k = left; //< merged subarray index
	while ((i <= mid - 1) && (j <= right)) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			temp[k++] = arr[j++];
			swaps = swaps + (mid - i);
		}
	}
	while (i <= mid - 1)
		temp[k++] = arr[i++];

	while (j <= right)
		temp[k++] = arr[j++];

	for (i = left; i <= right; i++)
		arr[i] = temp[i];

	return swaps;
}

int merge_sort(std::vector<int>& arr, std::vector<int>& temp, int left,
		int right) {
	int mid;
	if (right > left) {
		mid = (right + left) / 2; //< divide array to two parts

		merge_sort(arr, temp, left, mid);
		merge_sort(arr, temp, mid + 1, right);

		merge(arr, temp, left, mid + 1, right);
	}
	return swaps;
}

int inv_count(std::vector<int>& arr) {
	std::vector<int> temp(arr.size());
	return merge_sort(arr, temp, 0, arr.size() - 1);
}

int main(int argc, char **argv) {
	scanf("%u", &strLen);
	scanf("%s", jas);
	scanf("%s", malgosia);
	positions.resize(strLen);

	gen_positions();
	inv_count(positions);

	printf("%llu", swaps);

	return 0;
}

//Autor: Piotr Nosek

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;
queue <int> literki[26];
int gdzie[1000009];
long long load[1000009];

void add(int x, int v = 0)
{
    while(x <= n)
    {
        load[x]+=v;
        x += x & (-x);
    }
}

int query(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += load[x];
        x -= x & (-x);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    string jas, gosia;
    cin >> n;
    cin >> jas >> gosia;
    for(int i=0; i<n; i++)
        literki[static_cast<int>(jas[i] - 'A')].push(i+1);
    for(int i=1; i<=n; i++)
    {
        int pom = literki[static_cast<int>(gosia[i-1] - 'A')].front();
        literki[static_cast<int>(gosia[i-1] - 'A')].pop();
        gdzie[pom] = i;
    }
    unsigned long long wynik = 0;
    for(int i=1; i<=n; i++)
        add(gdzie[i]);
    for(int i=1; i<=n; i++)
    {
        long long tmp = query(gdzie[i]);
        add(gdzie[i], 1);
        wynik+=gdzie[i] - 1 - tmp;
    }
    cout << wynik;
    return 0;
}

//Autor: Piotr Nosek
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int tab[1007];
int najw[1007];
int numTab[1000007];
vector<int> roz[1007];
int n, maxx;
vector <int> pierwsze;

int abs(int a) {return a > 0 ? a : -a;}

void sito()
{
    for(int i=2; i*i<=maxx; i++)
    {
        if(numTab[i])
            continue;
        for(int j=2*i; j<=maxx; j+=i)
            numTab[j] = 1;
    }
    for(int i=2; i<=maxx; i++)
        if(!numTab[i])
            pierwsze.push_back(i);
}

int odl(int a, int b)
{
    int wynik = 0;
    if(tab[a] == 1)
    {
        for(int i=2; i<=najw[tab[b]]; i++)
            wynik+=roz[b][i];
        return wynik;
    }
    if(tab[b] == 1)
    {
        for(int i=2; i<=najw[tab[a]]; i++)
            wynik+=roz[a][i];
        return wynik;
    }
    for(int i=2; i<=max(najw[tab[a]], najw[tab[b]]); i++)
    {
       wynik+=abs(roz[a][i] - roz[b][i]);
    }
    return wynik;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> tab[i];
    int *tmp = max_element(tab, tab+n);
    maxx = tab[tmp - tab];
    sito();
    for(int i=0; i<n; i++)
        for(int j=0; j<maxx; j++)
            roz[i].push_back(0);
    for(int i=0; i<n; i++)
    {
        int liczba = tab[i], j = 0;
        while(liczba > 1)
        {
            if(liczba % pierwsze[j] == 0)
            {
                roz[i][pierwsze[j]]++;
                liczba /=pierwsze[j];
                najw[tab[i]] = pierwsze[j];
            }
            else j++;
        }
    }
    for(int i=0; i<n; i++)
    {
        int maks = 1000000, ix = 0;
        for(int j=0; j<n; j++)
        {
            if(j == i)
                continue;
            int danaOdl = odl(i, j);
            if(danaOdl < maks)
            {
                maks = danaOdl;
                ix = j;
            }
        }
        cout << ix+1 << "\n";
    }
    return 0;
}

#include <stdio.h>

int d[2123456], h[256], n[1123456];
char a[1123456], b[1123456];

int main(int argc, char** argv) {
    int z, i = scanf("%d %s %s", &z, a, b);
    long long int t = 0;
    for (i = z - 1; i >= 0; i--) {
        d[i * 2] = d[i * 2 + 1] = 0;
        n[i] = h[a[i]];
        h[a[i]] = i;
    }
    for (i = 0; i < z; i++) {
        int j, r = 0, p = h[b[i]];
        h[b[i]] = n[p];
        t += p;
        for (j = 0; (z >> j); j++) {
            t -= (p % 2) * (d[r + p / 2] += 1 - p % 2);
            r += (z + (2 << j) - 1) >> (j + 1);
            p /= 2;
        }
    }
    printf("%lld\n", t);
    return 0;
}