oj.uz

Submission #133076

# Submission time Handle Problem Language Result Execution time Memory
133076 2019-07-20T06:30:59 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 94092 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[j - i] == 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 22 ms 2296 KB Output is correct
2 Correct 24 ms 2344 KB Output is correct
3 Correct 15 ms 1400 KB Output is correct
4 Correct 25 ms 2296 KB Output is correct
5 Correct 25 ms 2168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2296 KB Output is correct
2 Correct 24 ms 2344 KB Output is correct
3 Correct 15 ms 1400 KB Output is correct
4 Correct 25 ms 2296 KB Output is correct
5 Correct 25 ms 2168 KB Output is correct
6 Correct 968 ms 93932 KB Output is correct
7 Correct 1312 ms 94092 KB Output is correct
8 Correct 1349 ms 88384 KB Output is correct
9 Correct 1334 ms 80632 KB Output is correct
10 Correct 1466 ms 92168 KB Output is correct
11 Correct 1445 ms 91188 KB Output is correct
12 Correct 1301 ms 82344 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2296 KB Output is correct
2 Correct 24 ms 2344 KB Output is correct
3 Correct 15 ms 1400 KB Output is correct
4 Correct 25 ms 2296 KB Output is correct
5 Correct 25 ms 2168 KB Output is correct
6 Correct 968 ms 93932 KB Output is correct
7 Correct 1312 ms 94092 KB Output is correct
8 Correct 1349 ms 88384 KB Output is correct
9 Correct 1334 ms 80632 KB Output is correct
10 Correct 1466 ms 92168 KB Output is correct
11 Correct 1445 ms 91188 KB Output is correct
12 Correct 1301 ms 82344 KB Output is correct
13 Execution timed out 1551 ms 2404 KB Time limit exceeded
14 Halted 0 ms 0 KB -