oj.uz

Submission #133077

# Submission time Handle Problem Language Result Execution time Memory
133077 2019-07-20T06:31:19 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1424 ms 94104 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const long long mod = 100000000007LL;

string S, T;
vector<long long> vec[3009];

long long power[3009]; bool nibeki[3009];

void init() {
	power[0] = 1LL;
	for (int i = 1; i <= 3000; i++) power[i] = (101LL * power[i - 1]);
	for (int i = 0; i <= 11; i++) nibeki[1 << i] = true;
}

long long hash_val(string &U) {
	long long r = 0;
	for (int i = 0; i < U.size(); i++) {
		r *= 101LL;
		r += (long long)(U[i] - 'a' + 1LL);
	}
	return r;
}

vector<long long> get_substring(string &U) {
	vector<long long> a, b, c;
	a.push_back(0);
	for (int i = 0; i < U.size(); i++) {
		a.push_back((101LL * a[a.size() - 1] + (long long)(U[i] - 'a' + 1)));
	}
	b.push_back(0);
	for (int i = U.size() - 1; i >= 0; i--) {
		b.push_back((b[b.size() - 1] + power[U.size() - 1 - i] * (long long)(U[i] - 'a' + 1)));
	}
	reverse(b.begin(), b.end());

	for (int i = 0; i < U.size(); i++) {
		long long s = a[i] + power[i] * b[i];
		c.push_back(s);
	}
	return c;
}

int main() {
	init();
	cin >> S >> T;
	for (int i = 0; i < S.size(); i++) {
		string G = "";
		for (int j = i + 1; j <= S.size(); j++) {
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[j - i] == false) continue;
			}
			G += S[j - 1];
			vector<long long> V1 = get_substring(G);
			for (int k = 0; k < V1.size(); k++) {
				vec[j - i].push_back((((V1[k] % mod) + mod) << 20) + 1LL * i);
			}
		}
	}
	for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());

	int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
	for (int i = 0; i < T.size(); i++) {
		string G = "";
		for (int j = i + 1; j <= T.size(); j++) {
			G += T[j - 1];
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[j - i] == false) continue;
			}
			long long v = hash_val(G); v = (v % mod) + mod;

			int pos1 = lower_bound(vec[j - i].begin(), vec[j - i].end(), v << 20) - vec[j - i].begin();
			if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
				if (maxn < j - i) {
					maxn = j - i;
					maxid = make_pair(vec[j - i][pos1] % (1LL << 20), i);
				}
			}
		}
	}

	for (int i = 1; i <= T.size(); i++) {
		string G = "";
		for (int j = i - 1; j >= 0; j--) {
			G += T[j];
			if (S.size() > 400 || T.size() > 400) {
				if (nibeki[i - j] == false) continue;
			}
			long long v = hash_val(G); v = (v % mod) + mod;

			int pos1 = lower_bound(vec[i - j].begin(), vec[i - j].end(), v << 20) - vec[i - j].begin();
			if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
				if (maxn < i - j) {
					maxn = i - j;
					maxid = make_pair(vec[i - j][pos1] % (1LL << 20), j);
				}
			}
		}
	}

	cout << maxn << endl;
	cout << maxid.first << " " << maxid.second << endl;
	return 0;
}

Compilation message

necklace.cpp: In function 'long long int hash_val(std::__cxx11::string&)':
necklace.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp: In function 'std::vector<long long int> get_substring(std::__cxx11::string&)':
necklace.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:53:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= S.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < V1.size(); k++) {
                    ~~^~~~~~~~~~~
necklace.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
                  ~~^~~~~~~~~~~
necklace.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:69:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= T.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos1 < vec[j - i].size() && (vec[j - i][pos1] >> 20) == v) {
        ~~~~~^~~~~~~~~~~~~~~~~~~
necklace.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= T.size(); i++) {
                  ~~^~~~~~~~~~~
necklace.cpp:96:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos1 < vec[i - j].size() && (vec[i - j][pos1] >> 20) == v) {
        ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2300 KB Output is correct
2 Correct 24 ms 2324 KB Output is correct
3 Correct 14 ms 1392 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 24 ms 2168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2300 KB Output is correct
2 Correct 24 ms 2324 KB Output is correct
3 Correct 14 ms 1392 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 24 ms 2168 KB Output is correct
6 Correct 985 ms 94068 KB Output is correct
7 Correct 1297 ms 94104 KB Output is correct
8 Correct 1323 ms 88280 KB Output is correct
9 Correct 1279 ms 80676 KB Output is correct
10 Correct 1424 ms 92040 KB Output is correct
11 Correct 1401 ms 91236 KB Output is correct
12 Correct 1270 ms 82452 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2300 KB Output is correct
2 Correct 24 ms 2324 KB Output is correct
3 Correct 14 ms 1392 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 24 ms 2168 KB Output is correct
6 Correct 985 ms 94068 KB Output is correct
7 Correct 1297 ms 94104 KB Output is correct
8 Correct 1323 ms 88280 KB Output is correct
9 Correct 1279 ms 80676 KB Output is correct
10 Correct 1424 ms 92040 KB Output is correct
11 Correct 1401 ms 91236 KB Output is correct
12 Correct 1270 ms 82452 KB Output is correct
13 Incorrect 140 ms 2376 KB Output isn't correct
14 Halted 0 ms 0 KB -