oj.uz

Submission #1003768

# Submission time Handle Problem Language Result Execution time Memory
1003768 2024-06-20T17:17:02 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
0 / 110
 4 ms 1776 KB 
#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;
			}
			ptr2++;
		}
	}

	Mergesort(0, n-1, fim);

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

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 4 ms 1776 KB Output isn't correct
3 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 Incorrect 4 ms 1776 KB Output isn't correct
3 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 Incorrect 4 ms 1776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 4 ms 1776 KB Output isn't correct
3 Halted 0 ms 0 KB -