Submission #1163504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163504		i271828	Ekoeko (COCI21_ekoeko)	C++20	0 / 110	785 ms	2288 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX=200005;

int N=4;
char A[MAX]="soolnlsn";
map<char,vector<int>> idxs;
vector<int> L;
vector<int> R;
int pos[MAX];
bool lr[MAX];
int mv[MAX][2];
int D[MAX];

int main(){
	cin>>N;	cin>>A;
	for (int i=0;i<2*N;i++){
		idxs[A[i]].push_back(i);
	}
	for (auto pr:idxs){
		char c=pr.first;
		int l=idxs[c].size();
		for (int i=0;i<l/2;i++){
			L.push_back(idxs[c][i]);
			R.push_back(idxs[c][l-1-i]);
		}
	}
	for (int i=0;i<L.size();i++){
		pos[L[i]]=i,pos[R[i]]=i;
		lr[L[i]]=1;
		lr[R[i]]=0;
		D[i]=(R[i]-L[i])-N;
	}
	for (int i=0;i<2*N;i++){
		int x=pos[i];
		int dist=D[x];
		if (dist<0 && !lr[i]){
			dist=-dist;
			for (int j=i;j<i+dist;j++){
				lr[j]  =  lr[j+1];
				pos[j] = pos[j+1];
				mv[pos[j]][lr[j]]-=1;
				lr[j] ? D[pos[j]]++ : D[pos[j]]--;
			}
			lr[i+dist]=0;
			pos[i+dist]=x;
			mv[x][0]+=dist;
			D[x]+=dist;
		}else if (dist>0 && lr[i]){
			for (int j=i;j<i+dist;j++){
				lr[j]  =  lr[j+1];
				pos[j] = pos[j+1];
				mv[pos[j]][lr[j]]-=1;
				lr[j] ? D[pos[j]]++ : D[pos[j]]--;
			}
			lr[i+dist]=1;
			pos[i+dist]=x;
			mv[x][1]+=dist;
			D[x]-=dist;
		}
	}
	ll ans=0;
	for (int i=0;i<N;i++){
		ans+=abs(mv[i][0]);
		ans+=abs(mv[i][1]);
		//cout<<L[i]<<' '<<R[i]<<'\n';
		//cout<<mv[i][0]<<' '<<mv[i][1]<<'\n';
	}
	cout<<ans/2;
}

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