oj.uz

Submission #872513

# Submission time Handle Problem Language Result Execution time Memory
872513 2023-11-13T08:59:27 Z HossamHero7 Ekoeko (COCI21_ekoeko) C++14
20 / 110
 4 ms 3376 KB 
#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

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.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #5
0 / 40.0

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