Submission #677074

#	Time	Username	Problem	Language	Result	Execution time	Memory
677074		SamNguyen	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	10 ms	3476 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define INPFILE "krokro.inp"
#define OUTFILE "krokro.out"
using lli = long long;

template <int N>
class BIT {
private:
    int n, bit[N + 7];

public:
    void init(int _n) {
        n = _n;
        memset(bit, 0, sizeof bit);
    }

    inline void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }

    inline int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) res += bit[i];
        return res;
    }
};

template <int N, class It>
lli COUNT_INVS(It sta, It fin) {
    static BIT<N> bit;
    bit.init(N);

    lli res = 0;
    auto it = fin;

    do {
        it--;
//        cerr << "*it = " << *it << endl;
        res += bit.get(*it - 1);
        bit.add(*it, +1);
    }
    while (it != sta);

    return res;
}

const int MAX = 3e5 + 7;
int N;
string str;

void input() {
    cin >> N >> str;
    str = "#" + str;
}

lli COUNT_DIVISION_SWAPS() {
    int cnt[26], ptr[26];
    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= 2 * N; i++)
        cnt[str[i] - 'a']++;

    static int tmp[MAX];

    memset(ptr, 0, sizeof ptr);
    for (int i = 1; i <= 2 * N; i++) {
        int c = str[i] - 'a';
        tmp[i] = (ptr[c] >= cnt[c] / 2) + 1;
        ptr[c]++;
    }

//    for (int i = 1; i <= 2 * N; i++)
//        cerr << tmp[i] << " ";
//    cerr << endl;

    string new_str = "#";
    for (int j : {1, 2})
        for (int i = 1; i <= 2 * N; i++) if (tmp[i] == j)
            new_str.push_back(str[i]);

    swap(str, new_str);

//    cerr << "str = " << str << endl;

    return COUNT_INVS<2>(tmp + 1, tmp + 2 * N + 1);
}

lli COUNT_REARRANGEMENT_SWAPS() {
    queue<int> inds[26];

    for (int i = 1; i <= N; i++) {
        inds[str[i] - 'a'].push(i);
//        cerr << str[i] << ": " << i << endl;
    }

    static int tmp[MAX];

    for (int i = 1; i <= N; i++) {
        int c = str[i + N] - 'a';
//        cerr << "c = " << c << " -> " << inds[c].front() << endl;
        tmp[i] = inds[c].front();
        inds[c].pop();
    }

    return COUNT_INVS<MAX>(tmp + 1, tmp + N + 1);
}

void solve() {
    lli ans = 0;
    ans += COUNT_DIVISION_SWAPS();
    ans += COUNT_REARRANGEMENT_SWAPS();
    cout << ans;
}

int main(void) {
    if (fopen(INPFILE, "r")) {
        freopen(INPFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    input();
    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(INPFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40