Submission #961015

#	Time	Username	Problem	Language	Result	Execution time	Memory
961015		Pety	Ekoeko (COCI21_ekoeko)	C++14	20 / 110	1093 ms	1508 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];

int CountSteps(string s1, string s2, int size)
{
    int i = 0, j = 0;
    int result = 0;
 
    // Iterate over the first string and convert
    // every element equal to the second string
    while (i < size) {
        j = i;
 
        // Find index element of first string which
        // is equal to the ith element of second string
        while (s1[j] != s2[i]) {
            j += 1;
        }
 
        // Swap adjacent elements in first string so
        // that element at ith position becomes equal
        while (i < j) {
 
            // Swap elements using temporary variable
            char temp = s1[j];
            s1[j] = s1[j - 1];
            s1[j - 1] = temp;
            j -= 1;
            result += 1;
        }
        i += 1;
    }
    return result;
}
 

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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40