Submission #1003771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003771		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	30 ms	3516 KiB

Main

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

#define int long long

int cnt=0;

void Merge(int l, int r, vector<int> &a){
	vector<int> s;
	int mid=(l+r)/2;
	int aux=0;

	int p1=l, p2=mid+1;
	while(p1<=mid && p2<=r){
		if(a[p1]<a[p2]){
			cnt+=aux;
			s.push_back(a[p1]);
			p1++;
		}
		else{
			aux++;
			s.push_back(a[p2]);
			p2++;
		}
	}

	while(p1<=mid){
		s.push_back(a[p1]);
		cnt+=aux;
		p1++;
	}
	while(p2<=r){
		s.push_back(a[p2]);
		p2++;
	}

	for(int i=0; i<s.size(); i++){
		a[l+i]=s[i];
	}
}

void Mergesort(int l, int r, vector<int> &a){
	if(l<r){
		int mid=(l+r)/2;
		Mergesort(l, mid, a);
		Mergesort(mid+1, r, a);
		Merge(l, r, a);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	string a;
	cin >> a;

	int c1[26]={}, c2[26]={};

	for(int i=0; i<(n<<1); i++){
		if(i<n)c1[a[i]-'a']++;
		c2[a[i]-'a']++;
	}

	int esq[26]={}, dir[26]={};

	for(int i=0; i<26; i++){
		c2[i]>>=1;
		if(c1[i]>c2[i]){
			esq[i]=c1[i]-c2[i];
		}
		else if(c1[i]<c2[i]){
			dir[i]=c2[i]-c1[i];
		}
	}

	int aaa=0, resp=0;

	string le="", ae="", ld="", ad="";

	for(int i=n-1; i>=0; i--){
		if(esq[a[i]-'a']>0){
			esq[a[i]-'a']--;
			resp+=n-1-aaa-i;
			aaa++;
			ad.push_back(a[i]);
		}
		else le.push_back(a[i]);
	}
	reverse(ad.begin(), ad.end());
	reverse(le.begin(), le.end());
	aaa=0;

	for(int i=n; i<2*n; i++){
		if(dir[a[i]-'a']>0){
			dir[a[i]-'a']--;
			resp+=i-n-aaa;
			aaa++;
			ae.push_back(a[i]);
		}
		else ld.push_back(a[i]);
	}

	resp+=aaa*aaa;

	le+=ae;
	ld=ad+ld;

	vector<int> fim(n);


	for(int i=0; i<26; i++){
		int ptr1=0, ptr2=0;
		char ch='a'+i;
		while(ptr2<n){
			if(ld[ptr2]==ch){
				while(le[ptr1]!=ch )ptr1++;
				fim[ptr1]=ptr2;
				ptr1++;
			}
			ptr2++;
		}
	}

	// cout << le << endl << ld << endl << resp << endl;
	// for(auto &x:fim)
	// 	cout << x << ' ';
	// cout << endl;

	Mergesort(0, n-1, fim);

	cout << resp+cnt << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void Merge(long long int, long long int, std::vector<long long int>&)':
Main.cpp:37:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~

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