제출 #1163468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163468		yhkhoo	Ekoeko (COCI21_ekoeko)	C++17	20 / 110	1093 ms	2112 KiB

Main

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

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int n;
	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] << ' ';
	}
	int loc[n]; // fw
	for(int i=0; i<n; i++){
		loc[i] = i;
	}
	for(int i=0; i<n; i++){
		ans += loc[ts[i]] - i;
		for(int j=0; j<ts[i]; j++){
			loc[j]++;
		}
	}
	cout << ans;
	return 0;
}

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