oj.uz

Submission #536427

# Submission time Handle Problem Language Result Execution time Memory
536427 2022-03-13T09:50:37 Z inksamurai Ekoeko (COCI21_ekoeko) C++17
0 / 110
 14 ms 2908 KB 
#include <bits/stdc++.h>
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){
		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);
			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);
			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]));
		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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 6 ms 1292 KB Output is correct
3 Correct 11 ms 2144 KB Output is correct
4 Incorrect 14 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 6 ms 1292 KB Output is correct
3 Correct 11 ms 2144 KB Output is correct
4 Incorrect 14 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 6 ms 1292 KB Output is correct
3 Correct 11 ms 2144 KB Output is correct
4 Incorrect 14 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 6 ms 1292 KB Output is correct
3 Correct 11 ms 2144 KB Output is correct
4 Incorrect 14 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -