oj.uz

Submission #961015

# Submission time Handle Problem Language Result Execution time Memory
961015 2024-04-11T11:35:19 Z Pety Ekoeko (COCI21_ekoeko) C++14
20 / 110
 1000 ms 1508 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 278 ms 1072 KB Output is correct
3 Execution timed out 1093 ms 1508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 278 ms 1072 KB Output is correct
3 Execution timed out 1093 ms 1508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 278 ms 1072 KB Output is correct
3 Execution timed out 1093 ms 1508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 278 ms 1072 KB Output is correct
3 Execution timed out 1093 ms 1508 KB Time limit exceeded
4 Halted 0 ms 0 KB -