Submission #961020

#	Time	Username	Problem	Language	Result	Execution time	Memory
961020		Pety	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	14 ms	3656 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6+2;
const int mod = 1e9 + 7;

string s;
int n, fr[2][26], total[26], plm[200002];

struct AIB {
  int n;
  vector<int>aib;
  AIB(int N): n(N), aib(N+2) {}
  void update (int x, int val) {
    for (int i = x; i <= n; i += (i & -i))
      aib[i] += val;
  }
  int query (int x) {
    int s = 0;
    for (int i = x; i; i -= (i & -i))
      s += aib[i];
    return s;
  }
};
using ll = long long;

ll CountSteps(string s1, string s2, int size)
{
    AIB pom(size);
    deque<int>poz[26];
    for (int i = 0; i < size; i++)
      poz[s1[i] - 'a'].push_back(i);
    ll ans = 0;
    for (int i = 0; i < size; i++) {
      int k = poz[s2[i] - 'a'].front();
      poz[s2[i] - 'a'].pop_front();
      ans += pom.query(size - k);
      pom.update(size - k, 1);
    }
    return ans;
}
 

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  cin >> s;
  for (int i = 0; i < 2 * n; i++) {
    fr[i / n][s[i] - 'a']++;
  }
  for (int i = 0; i < 26; i++)
    total[i] = fr[0][i] + fr[1][i];
  deque<char>q1, q2;
  int stop = n;
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (fr[0][s[i] - 'a'] > total[s[i] - 'a'] / 2) {
      ans += stop - i;
      stop--;
      q1.push_front(s[i]);
      plm[i] = '?';
      fr[0][s[i] - 'a']--;
    }
  }
  stop = n-1;
  for (int i = n; i < 2 * n; i++) {
    if (fr[1][s[i] - 'a'] > total[s[i] - 'a'] / 2) {
      q2.push_back(s[i]);
      ans += i - stop;
      stop++;
      plm[i] = '?';
      fr[1][s[i] - 'a']--;
    }
  }
  string a, b;
  for (int i = 0; i < n; i++)
    if (plm[i] != '?')
      a += s[i];  
  for (auto it : q2) a += it;
  for (auto it : q1) b += it;
  for (int i = n; i < 2 * n; i++)
     if (plm[i] != '?')
      b += s[i];
  //cout << a << " " << b << "\n";
  cout << CountSteps(a, b, n) + CountSteps(s, a + b, 2 * n);
  return 0;
}

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