Submission #2706489

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 998244353
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 300003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;
bool ya[mx];
string ss;
int n,bit[mx],a[mx],kanan[mx];
vector<int>isi[30];
long long jaw=0;

int cari(int idx){
	int ret=0;
	for(;idx;idx-=idx&-idx)ret+=bit[idx];
	return ret;
}

void upd(int idx){
	for(;idx<=n;idx+=idx&-idx)bit[idx]++;
}

int main(){
	cin>>ss;
	n=ss.length();
	for(int i=0;i<n;i++){
		a[i]=ss[i]-'a';
	}	
	for(int i=0;i<n;i++){
		isi[a[i]].pb(i);
	}
	int cnt=0;
	for(int i=0;i<26;i++){
		if(isi[i].size()%2==1)cnt++;
	}
	if(cnt>=2){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<26;i++){
		int r=isi[i].size()-1;
		for(int j=0;j<isi[i].size();j++){
			if(j>r)break;
		//	debug(j);
		//	debug(r);
			if(j==r)ya[isi[i][j]]=true;
			kanan[isi[i][r]]=kanan[isi[i][j]]=isi[i][r];
			r--;
		}
	}
	int sim=-1;
	for(int i=0;i<n;i++){
		//if(ya[i])debug(i);
		if(ya[i]){
			sim=i;
			continue;
		}
		if(kanan[i]!=i)jaw=jaw+cari(kanan[i]);
	//	debug(jaw);
	//	cout<<"----\n";
		upd(kanan[i]+1);
	//	cout<<"////\n";
	}
	if(sim!=-1){
		for(int i=0;i<n;i++){
			if(i==sim)continue;
			if(kanan[i]==i)continue;
			if(i<sim && kanan[i]>sim)continue;
			jaw++;
		}
	}
	cout<<jaw<<endl;
}

Submission Info

Judge Result