Submission #116845

#	Time	Username	Problem	Language	Result	Execution time	Memory
116845		MrUnknown	Lozinke (COCI17_lozinke)	C++11	15 / 100	1084 ms	1704 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;
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);
}
bool ktra(string substr, string str) {
	int z[15],l,r;
	for (int i=0;i<str.size();i++) {
		if (i==0||i>r) {
			l=r=i;
			while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
			if (r-l==substr.size()) return true;
			z[l]=r-l;
			r--;
		} else {
			int k=i-l;
			if (z[k]<=r-i) z[i]=z[k];
			else {
				l=i;
				while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
				if (r-l==substr.size()) return true;
				z[i]=r-l;
				r--;
			}
		}
	}
	return false;
}
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=n;i>=1;i--) {
//		cout<<s[i]<<" ";
//	}
//	cout<<"\n";
	for (int i=n;i>1;i--) {
		for (int j=i-1;j>=1;j--) {
			if (i!=j) {
				if (ktra(s[j],s[i])) {
					dem++;
					if (s[j].size()==s[i].size()) dem++;
//					cout<<s[j]<<" "<<s[i]<<"\n";
				}
//				if (s[j].size()<=s[i].size()) 
//				if (s[i].size()<=s[j].size()) if (ktra(s[i],s[j])) dem++;
			}
		}
	}
	printf("%lld", dem);
	return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'bool ss(int, int)':
lozinke.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<s[x].size();i++) {
               ~^~~~~~~~~~~~
lozinke.cpp: In function 'bool ktra(std::__cxx11::string, std::__cxx11::string)':
lozinke.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<str.size();i++) {
               ~^~~~~~~~~~~
lozinke.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
           ~~~^~~~~~~~~~~~~~
lozinke.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (r-l==substr.size()) return true;
        ~~~^~~~~~~~~~~~~~~
lozinke.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (r-l<substr.size()&&str[r]==substr[r-l]) r++;
            ~~~^~~~~~~~~~~~~~
lozinke.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (r-l==substr.size()) return true;
         ~~~^~~~~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
lozinke.cpp: In function 'bool ktra(std::__cxx11::string, std::__cxx11::string)':
lozinke.cpp:50:15: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if (z[k]<=r-i) z[i]=z[k];
              ~^~
lozinke.cpp:49:8: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int k=i-l;
        ^

• Subtask 1: 15 / 100