Submission #872513

#	Time	Username	Problem	Language	Result	Execution time	Memory
872513		HossamHero7	Ekoeko (COCI21_ekoeko)	C++14	20 / 110	4 ms	3376 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
struct BIT{
	vector<int> bit;	
	BIT(int n){
		bit.resize(n+1);
	}
	BIT(vector<int> &v){
		bit = v;
		for(int i=1;i<v.size();i++){
			bit[i+(i&(-i))] += bit[i];
		}
	}
	ll prefix(int i){
		ll ret = 0;
		while(i>0){
			ret += bit[i];
			i -= i&(-i);	
		}
		return ret;
	}
	ll sumQ(int l,int r){
		return prefix(r)-prefix(l-1);
	}
	void update(int x,int val){
		while(x<bit.size()){
			bit[x] += val;
			x += x&(-x);
		}
	}
};
ll minSwaps(string s1,string s2){
	int n = s1.size();
    BIT tree1(n+5);
	vector<vector<int>> idx1(27);
	vector<vector<int>> idx2(27);
	for(int i=0;i<n;i++){
		idx1[s1[i]-'a'].push_back(i);
		idx2[s2[i]-'a'].push_back(i);
	}
	vector<int> a(n);
	for(int i=0;i<26;i++){
		for(int j=0;j<idx1[i].size();j++){
			a[idx1[i][j]] = idx2[i][j];
		}
	}
	ll ans = 0;
	for(int i=0;i<n;i++){
		ans += tree1.sumQ(a[i]+2,n+1);
		tree1.update(a[i]+1,1);
	}
    return ans;
}
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> frq(26);
    for(int i=0;i<2*n;i++) frq[s[i]-'a'] ++;
    vector<char> cnt(26);
    string tar = "";
    for(int i=0;i<2*n;i++){
        if(cnt[s[i]-'a'] < frq[s[i]-'a']/2) tar += s[i];
        cnt[s[i]-'a'] ++;
    }
    tar += tar;
    cout<<minSwaps(s,tar)<<endl;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);		 cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'BIT::BIT(std::vector<long long int>&)':
Main.cpp:13: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]
   13 |   for(int i=1;i<v.size();i++){
      |               ~^~~~~~~~~
Main.cpp: In member function 'void BIT::update(long long int, long long int)':
Main.cpp:29:10: 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]
   29 |   while(x<bit.size()){
      |         ~^~~~~~~~~~~
Main.cpp: In function 'll minSwaps(std::string, std::string)':
Main.cpp:46: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]
   46 |   for(int j=0;j<idx1[i].size();j++){
      |               ~^~~~~~~~~~~~~~~

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