Submission #1163437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163437		Ruichen	Ekoeko (COCI21_ekoeko)	C++20	0 / 110	2 ms	580 KiB

Main

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

signed main(){
	int n, ans=0;
	cin >> n;
	string s;
	cin >> s;
	vector<int> a(26,0), c(26,0);
	for(int i=0; i<n; i++){
		a[s[i]-'a']++;
		a[s[n+i]-'a']++;
		c[s[i]-'a']++;
	}
	string ms1="", ms2="", fs1="", fs2="";
	int p=0;
	for(int i=n-1; i>=0; i--){
		if(c[s[i]-'a']>a[s[i]-'a']/2){
			c[s[i]-'a']--;
			ans+=n-i-1-p;
			p++;
			ms1+=s[i];
		}
		else{
			fs1+=s[i];
		}
	}
	p=0;
	for(int i=n; i<n*2; i++){
		if(c[s[i]-'a']<a[s[i]-'a']/2){
			c[s[i]-'a']++;
			ans+=i-n-p;
			p++;
			ms2+=s[i];
		}
		else{
			fs2+=s[i];
		}
	}
	ans+=p*p;
	//cout  << fs1 << " " << fs2 << " " << ms1  << " " << ms2 << endl;
	stack<char> t;
	for(int i=0; i<(long long)fs1.length(); i++){
		t.push(fs1[i]);
	}
	for(int i=0; i<(long long)fs1.length(); i++){
		fs1[i]=t.top();
		t.pop();
	}
	for(int i=0; i<(long long)ms1.length(); i++){
		t.push(ms1[i]);
	}
	for(int i=0; i<(long long)ms1.length(); i++){
		ms1[i]=t.top();
		t.pop();
	}
	fs1=fs1+ms2;
	fs2=ms1+fs2;
	unordered_set<char> us;
	for(int i=n-1; i>=0; i--){
		us.insert(fs2[i]);
	}
	for(int i=0; i<n; i++){
		ans+=distance(us.begin(),us.find(fs1[i]));
		us.erase(us.find(fs1[i]));
	}
	cout << ans << endl;
}

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