Untitled

mail@pastecode.io avatar
unknown
plain_text
22 days ago
1.5 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100000;
int n;
string a[MAXN];
struct kq
{
	string item;
	int count;
};
kq res[MAXN];
void nhap()
{
	cin>>n;
	for(int i=0;i<=n;i++)
	 getline(cin,a[i]);
}
int ss(string a, string b)
{
	if(a.size()<b.size()) return -1;
	if(a.size()>b.size()) return 1;
	for(int i=0;i<a.size();i++)
	 if(a[i]<b[i]) return -1;
	 else if(a[i]>b[i]) return 1;
	return 0;
}
int ss2(kq a, kq b)
{
	if(a.count==b.count) return ss(a.item,b.item);
	if(a.count>b.count) return -1;
	else return 1;
}
void sx(string a[], int l, int r)
{
	int mid=(l+r)/2;
	int i=l,j=r;
	while(i<=j)
	{
		while(ss(a[i],a[mid])<0) i++;
		while(ss(a[j],a[mid])>0) j--;
		if(i<=j)
		{
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	if(l<i) sx(a,l,mid-1);
	if(r>j) sx(a,mid+1,r);
}
void sx2(kq a[], int l, int r)
{
	int mid=(l+r)/2;
	int i=l,j=r;
	while(i<=j)
	{
		while(ss2(a[i],a[mid])<0) i++;
		while(ss2(a[j],a[mid])>0) j--;
		if(i<=j)
		{
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	if(l<i) sx2(a,l,mid-1);
	if(r>j) sx2(a,mid+1,r);
}
void xuly(string a[])
{
	a[n+1]=' ';
	kq res[MAXN];
	sx(a,1,n);
	int d=0;
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(a[i+1]==a[j]) i++;
		d++;
		res[d].item=a[j];
		res[d].count=(i-j)+1;
	}
	sx2(res,1,d);
	for(int i=1;i<=d;i++)
	 cout<<res[i].item<<" "<<res[i].count<<'\n';
}
int main()
{
	nhap();
	xuly(a);
	return 0;
}
Leave a Comment