Submission #824492

#	Time	Username	Problem	Language	Result	Execution time	Memory
824492		christinelynn	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	3364 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int merge(vector<int> &a, int l, int r);
int number_of_inversions(vector<int> &a, int l=0, int r=n-1) {
  if(l>=r) return 0;
  int mid=l+r>>1, ret=0;
  ret+=number_of_inversions(a, l, mid);
  ret+=number_of_inversions(a, mid+1, r);
  ret+=merge(a, l, r);
  return ret;
}
int merge(vector<int> &a, int l, int r) {
  vector<int> temp(r-l+1);
  int mid=l+r>>1;
  int i=l, j=mid+1, k=0, ret=0;
  while(i<=mid && j<=r) {
    if(a[i]<=a[j]) temp[k++]=a[i++];
    else temp[k++]=a[j++], ret+=mid-i+1;
  }
  while(i<=mid) temp[k++]=a[i++];
  while(j<=r) temp[k++]=a[j++];
  for(int I=l; I<=r; I++) a[I]=temp[I-l];
  return ret;
}
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string s; 
  cin >> n >> s;
  vector<int> a, cnt(26);
  vector<deque<int>> idx(26);
  vector<bool> vis(2*n);
  for(char c : s) cnt[c-'a']++;
  for(int &p : cnt) p>>=1;
  int ans=0, pre=0;
  for(int i=0; i<2*n; i++) {
    if(cnt[s[i]-'a']) {
      cnt[s[i]-'a']--;
      vis[i]=1;
      idx[s[i]-'a'].push_back(i);
      ans+=pre;
    } else pre++;
  }
  for(int i=0; i<2*n; i++) {
    if(vis[i]) continue;
    a.push_back(idx[s[i]-'a'].front());
    idx[s[i]-'a'].pop_front();
  }
  ans+=number_of_inversions(a);
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int number_of_inversions(std::vector<long long int>&, long long int, long long int)':
Main.cpp:8:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |   int mid=l+r>>1, ret=0;
      |           ~^~
Main.cpp: In function 'long long int merge(std::vector<long long int>&, long long int, long long int)':
Main.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int mid=l+r>>1;
      |           ~^~

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