Submission #1163479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163479		yhkhoo	Ekoeko (COCI21_ekoeko)	C++17	20 / 110	7 ms	2112 KiB

Main

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

#define lsb(x) ((x) & (-x))

const int MAXN = 100001;
int n;
int fw[MAXN];

void update(int X, int V){
	X++;
	while(X<=n){
		fw[X] += V;
		X += lsb(X);
	}
}

int query(int R){
	R++;
	int res = 0;
	while(R){
		res += fw[R];
		R -= lsb(R);
	}
	return res;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n;
	char s[2*n];
	cin >> s;
	int cnt[26];
	memset(cnt, 0, sizeof(cnt));
	for(int i=0; i<2*n; i++){
		cnt[s[i] - 'a']++;
	}
	int cna[26];
	for(int i=0; i<26; i++){
		cna[i] = cnt[i] / 2;
		//cerr << cna[i] << ' ';
	}
	//cerr << '\n';
	char s1[n], s2[n];
	auto s1p = s1, s2p = s2;
	int ans = 0;
	for(int i=0; i<2*n; i++){
		if(cna[s[i] - 'a']){
			ans += i - (s1p - s1);
			*s1p = s[i];
			s1p++;
			cna[s[i] - 'a']--;
		}
		else{
			*s2p = s[i];
			s2p++;
		}
	}
	// cerr << s1 << '\n' << s2;
	// cerr << ans << '\n';
	vector<int> locs[26];
	for(int i=0; i<n; i++){
		locs[s2[i] - 'a'].push_back(i);
	}
	/*for(int i=0; i<26; i++){
		cerr << i << ' ';
		for(auto j: locs[i]){
			cerr << j << ' ';
		}
		cerr << '\n';
	}*/
	int lp[26];
	memset(lp, 0, sizeof(lp));
	int ts[n];
	for(int i=0; i<n; i++){
		auto t = s1[i] - 'a';
		ts[i] = locs[t][lp[t]];
		lp[t]++;
		// cerr << ts[i] << ' ';
	}
	for(int i=1; i<n; i++){
		update(i, 1);
	}
	for(int i=0; i<n; i++){
		/*for(int i=0; i<n; i++){
			cerr << query(i) << ' ';
		}
		cerr << '\n';*/
		ans += query(ts[i]) - i;
		update(0, 1);
		update(ts[i], -1);
	}
	cout << ans;
	return 0;
}

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