oj.uz

Submission #133045

# Submission time Handle Problem Language Result Execution time Memory
133045 2019-07-20T05:55:42 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 17348 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

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

vector<long long> get_substring(string U) {
	vector<long long> a;
	for (int i = 0; i < U.size(); i++) {
		long long r = 0, cx = i;
		for (int j = 0; j < U.size(); j++) {
			r *= 100LL;
			r += (long long)(U[cx] - 'a' + 1LL);
			r %= 2147483647LL;
			cx++; if (cx == U.size()) cx = 0;
		}
		a.push_back(r);
	}
	return a;
}

int main() {
	cin >> S >> T;
	for (int i = 0; i < S.size(); i++) {
		for (int j = i + 1; j <= S.size(); j++) {
			string G = S.substr(i, j - i);
			vector<long long> V1 = get_substring(G); reverse(G.begin(), G.end());
			vector<long long> V2 = get_substring(G);
			for (int k = 0; k < V1.size(); k++) vec[j - i].push_back(make_pair(V1[k], i));
			for (int k = 0; k < V2.size(); k++) vec[j - i].push_back(make_pair(V2[k], 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++) {
		for (int j = i + 1; j <= T.size(); j++) {
			string G = T.substr(i, j - i);
			long long v = hash_val(G);
			
			int pos1 = lower_bound(vec[j - i].begin(), vec[j - i].end(), make_pair(v, 0)) - vec[j - i].begin();
			if (pos1 < vec[j - i].size() && vec[j - i][pos1].first == v) {
				if (maxn < j - i) {
					maxn = j - i;
					maxid = make_pair(vec[j - i][pos1].second, i);
				}
			}
		}
	}
	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:12: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:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < U.size(); j++) {
                   ~~^~~~~~~~~~
necklace.cpp:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    cx++; if (cx == U.size()) cx = 0;
              ~~~^~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= S.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < V1.size(); k++) vec[j - i].push_back(make_pair(V1[k], i));
                    ~~^~~~~~~~~~~
necklace.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < V2.size(); k++) vec[j - i].push_back(make_pair(V2[k], i));
                    ~~^~~~~~~~~~~
necklace.cpp:46: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:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:50:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j <= T.size(); j++) {
                       ~~^~~~~~~~~~~
necklace.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos1 < vec[j - i].size() && vec[j - i][pos1].first == v) {
        ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7544 KB Output is correct
2 Correct 159 ms 7416 KB Output is correct
3 Correct 71 ms 3960 KB Output is correct
4 Correct 163 ms 7472 KB Output is correct
5 Correct 150 ms 7040 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7544 KB Output is correct
2 Correct 159 ms 7416 KB Output is correct
3 Correct 71 ms 3960 KB Output is correct
4 Correct 163 ms 7472 KB Output is correct
5 Correct 150 ms 7040 KB Output is correct
6 Execution timed out 1560 ms 17348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7544 KB Output is correct
2 Correct 159 ms 7416 KB Output is correct
3 Correct 71 ms 3960 KB Output is correct
4 Correct 163 ms 7472 KB Output is correct
5 Correct 150 ms 7040 KB Output is correct
6 Execution timed out 1560 ms 17348 KB Time limit exceeded
7 Halted 0 ms 0 KB -