oj.uz

Submission #116864

# Submission time Handle Problem Language Result Execution time Memory
116864 2019-06-14T02:58:47 Z MrUnknown Lozinke (COCI17_lozinke) C++11
75 / 100
 1000 ms 17272 KB 
//#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;
	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

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

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 13 ms 1408 KB Output is correct
6 Correct 22 ms 1408 KB Output is correct
7 Correct 28 ms 2040 KB Output is correct
8 Correct 46 ms 2936 KB Output is correct
9 Correct 182 ms 2900 KB Output is correct
10 Correct 387 ms 8028 KB Output is correct
11 Correct 361 ms 4600 KB Output is correct
12 Execution timed out 1042 ms 17272 KB Time limit exceeded
13 Execution timed out 1052 ms 3192 KB Time limit exceeded
14 Correct 716 ms 15352 KB Output is correct
15 Execution timed out 1079 ms 15244 KB Time limit exceeded
16 Execution timed out 1077 ms 2296 KB Time limit exceeded
17 Execution timed out 1073 ms 1548 KB Time limit exceeded
18 Correct 846 ms 1488 KB Output is correct
19 Correct 818 ms 9060 KB Output is correct
20 Correct 633 ms 1540 KB Output is correct