Submission #536439

#	Time	Username	Problem	Language	Result	Execution time	Memory
536439		inksamurai	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	17 ms	4952 KiB

Main

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3HspL4A ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class T,class...E>
void print(const T&v,const E&...u){cout<<v<<' ',print(u...);}
// e

struct fenwick{
	int n;
	vector <int> bit;
	fenwick(int m){
		init(m);
	}
	void init(int m){
		n=m;
		bit.resize(n,0);
	}
	int get(int i){
		int s=0;
		while(i){
			s+=bit[i];
			i-=i&-i;
		}
		return s;
	}
	void add(int i,int x){
		while(i<=n){
			bit[i]+=x;
			i+=i&-i;
		}
	}
};

signed main(){
_3HspL4A;
	int n;
	cin>>n;
	string s;
	cin>>s;
	const int m=2*n;
	vec(vi) ids(26);
	rep(i,m){
		ids[s[i]-'a'].pb(i);
	}
	vi cnt(26);
	rep(i,26){
		int now=0;
		for(auto j:ids[i]){
			if(j<=n-1) cnt[i]+=1;
			else cnt[i]-=1;
		}
	}
	vi ndl,ndr;
	rep(i,26){
		if(cnt[i]>0){
			assert(cnt[i]%2==0);
			while(ids[i].back()>=n) ids[i].pop_back();
			rep(j,cnt[i]/2){
				ndl.pb(ids[i][sz(ids[i])-j-1]);
			}
		}else if(cnt[i]<0){
			assert(abs(cnt[i])%2==0);
			reverse(ids[i].begin(),ids[i].end());
			while(ids[i].back()<n) ids[i].pop_back();
			reverse(ids[i].begin(),ids[i].end());
			rep(j,abs(cnt[i]/2)){
				ndr.pb(ids[i][j]);
			}
		}
	}
	sort(ndl.begin(),ndl.end());
	sort(ndr.begin(),ndr.end());
	int ans=0;
	string sl="",sr="",adl="",adr="";
	{
		vi usd(m,0);
		for(auto v:ndl) usd[v]=1;
		for(auto v:ndr) usd[v]=1;
		int r=n-1;
		rep(i,n){
			if(!usd[i]){
				sl+=s[i];
			}else{
				ans+=r-i;
				r-=1;
				adl+=s[i];
			}
		}
		int l=n;
		rng(i,n,m){
			if(!usd[i]){
				sr+=s[i];
			}else{
				ans+=i-l;
				l+=1;
				adr+=s[i];
			}
		}
		ans+=sz(adr)*sz(adr);
	}
	sl+=adr;
	sr=adl+sr;
	rep(i,26){
		ids[i].clear();
	}
	rep(i,n){
		ids[sr[i]-'a'].pb(i);
	}
	rep(i,26){
		reverse(ids[i].begin(),ids[i].end());
	}
	fenwick bit(n+11);
	rep(i,n){
		int ch=sl[i]-'a';
		assert(sz(ids[ch]));
		// if(sz(ids[ch])==0){
		// 	print("nanii");
		// 	return 0;
		// }
		int j=ids[ch].back();
		ans+=j+bit.get(j+1)-i;
		bit.add(1,1);
		bit.add(j+2,-1);
		ids[ch].pop_back();
	}
	print(ans);
//	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:60:7: warning: unused variable 'now' [-Wunused-variable]
   60 |   int now=0;
      |       ^~~

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