oj.uz

Submission #87177

# Submission time Handle Problem Language Result Execution time Memory
87177 2018-11-29T22:17:27 Z jasony123123 Lozinke (COCI17_lozinke) C++11
15 / 100
 701 ms 41780 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define MOD1 1000000009LL
#define MOD2 2038072819LL
#define PRI1 610639LL
#define PRI2 949957LL

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

map<ll, set<int>> substrKey;
int N;
ll hsh[20000];

ll calcHsh(string &str, int i, int j) {
	ll p1 = 1;
	ll ret1 = 0;
	FORE(x, i, j) {
		ret1 += (ll)(str[x])*p1;
		ret1 %= MOD1;
		p1 *= PRI1;
		p1 %= MOD1;
	}
	ll p2 = 1;
	ll ret2 = 0;
	FORE(x, i, j) {
		ret2 += (ll)(str[x])*p2;
		ret2 %= MOD2;
		p2 *= PRI2;
		p2 %= MOD2;
	}
	return ret1^ret2;
}

void setup(string &str, int idx) {
	FOR(i,0,str.size()) FOR(j, i, str.size()) {
		ll curhsh = calcHsh(str, i, j);
		substrKey[curhsh].insert(idx);
		if (i == 0 && j == str.size() - 1)
			hsh[idx] = curhsh;
	}
}

int main() {
	//io();
	cin >> N;
	FOR(i, 0, N) {
		string str;
		cin >> str;
		setup(str, i);
	}
	ll ans = 0;
	FOR(i, 0, N) {
		ans += substrKey[hsh[i]].size() - 1;
	}
	cout << ans << "\n";
	return 0;
}


void io() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message

lozinke.cpp: In function 'void setup(std::__cxx11::string&, int)':
lozinke.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == 0 && j == str.size() - 1)
                 ~~^~~~~~~~~~~~~~~~~
lozinke.cpp: In function 'void io()':
lozinke.cpp:80:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:81:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Incorrect 3 ms 508 KB Output isn't correct
4 Incorrect 4 ms 560 KB Output isn't correct
5 Incorrect 14 ms 1644 KB Output isn't correct
6 Incorrect 22 ms 2368 KB Output isn't correct
7 Incorrect 29 ms 3180 KB Output isn't correct
8 Correct 37 ms 4972 KB Output is correct
9 Incorrect 122 ms 9904 KB Output isn't correct
10 Incorrect 286 ms 20144 KB Output isn't correct
11 Incorrect 250 ms 20144 KB Output isn't correct
12 Incorrect 658 ms 40748 KB Output isn't correct
13 Incorrect 522 ms 40748 KB Output isn't correct
14 Incorrect 446 ms 40748 KB Output isn't correct
15 Incorrect 701 ms 41780 KB Output isn't correct
16 Incorrect 594 ms 41780 KB Output isn't correct
17 Correct 231 ms 41780 KB Output is correct
18 Correct 113 ms 41780 KB Output is correct
19 Incorrect 509 ms 41780 KB Output isn't correct
20 Incorrect 241 ms 41780 KB Output isn't correct