Submission #116858

#	Time	Username	Problem	Language	Result	Execution time	Memory
116858		MrUnknown	Lozinke (COCI17_lozinke)	C++11	90 / 100	1073 ms	16636 KiB

lozinke

//#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define f_(i,a,b) for (int i=a;i>=b;i--)
//#define f(i,a,b) for (int i=a;i<=b;i++)

int n;
string s[20005];
long long dem=0;
map<string,bool> mb;
map<string,ll> m;
bool ss(int x,int y) {
	if (s[x].size()>s[y].size()) return false;
	if (s[x].size()<s[y].size()) return true;
	for (int i=0;i<s[x].size();i++) {
		if (s[x][i]>s[y][i]) return false;
		if (s[x][i]<s[y][i]) return true;
	}
	return true;
}
void xot(int l,int r) {
	if (l>=r) return ;
	int pos;
	pos=l;
	string si;
	for (int i=l;i<r;i++) {
		if (ss(i,r)) {
			si=s[i];
			s[i]=s[pos];
			s[pos]=si;
			pos++;
		}
	}
	si=s[r];
	s[r]=s[pos];
	s[pos]=si;
	xot(l,pos-1);
	xot(pos+1,r);
}
int main() {
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	scanf("%d", &n);
	for (int i=1;i<=n;i++) {
		cin>>s[i];
	}
	xot(1,n);
	for (int i=1;i<=n;i++) {
		mb.clear();
		for (int j=0;j<s[i].size();j++) {
			string si;
			for (int l=j;l<s[i].size();l++) {
				si=si+s[i][l];
				if (!mb[si]) {
					mb[si]=true;
					dem+=m[si];
				}
			}
		}
		dem+=m[s[i]];
		m[s[i]]++;
	}
	printf("%lld", dem);
	return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'bool ss(int, int)':
lozinke.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<s[x].size();i++) {
               ~^~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<s[i].size();j++) {
                ~^~~~~~~~~~~~
lozinke.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l=j;l<s[i].size();l++) {
                 ~^~~~~~~~~~~~
lozinke.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

• Subtask 1: 90 / 100