oj.uz

Submission #522809

# Submission time Handle Problem Language Result Execution time Memory
522809 2022-02-06T00:07:45 Z LucaDantas Necklace (Subtask 1-3) (BOI19_necklace1) C++17
29 / 85
 1500 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3010, p = 31;
constexpr long long mod = 1000000007;

struct StringHash {
	string s;

	long long a[maxn], pot[maxn];

	void build() {
		int n = (int)s.size();
		a[0] = s[0]-'a';
		pot[0] = 1;
		
		for(int i = 1; i < maxn; i++)
			pot[i] = pot[i-1] * p % mod;

		for(int i = 1; i < n; i++)
			a[i] = (a[i-1]*p + (s[i]-'a')) % mod; 
	}

	long long get(int l, int r) {
		return ( a[r] - (l ? a[l-1]*pot[r-l+1]%mod : 0) + mod ) % mod;
	}
} A, B;

int main() {
	cin >> A.s >> B.s;

	pair<int, pair<int,int>> ans = {-1, {-1, -1}};

	A.build();
	for(int SLA = 0; SLA < 2; SLA++) {
		B.build();
		for(int l = 0; l < (int)A.s.size(); l++) {
			for(int r = 0; r < (int)B.s.size(); r++) {
				if(A.s[l] != B.s[r]) continue;
				
				int sz1 = 0, sz2 = 0;
				
				for(int lg = 12; lg >= 0; lg--) {
					sz1 += 1<<lg;

					if(l+sz1-1 >= A.s.size() ||
						r+sz1-1 >= B.s.size() ||
							A.get(l, l+sz1-1) != B.get(r, r+sz1-1))
							sz1 -= 1<<lg;
				}

				for(int lg = 12; lg >= 0; lg--) {
					sz2 += 1<<lg;
					if(l+sz1+sz2-1 >= A.s.size() ||
						r-sz2 < 0 ||
							A.get(l+sz1, l+sz1+sz2-1) != B.get(r-sz2, r-1))
							sz2 -= 1<<lg;
				}

				ans = max(ans, {sz1+sz2, {l,  SLA ? B.s.size() - (r+sz1) : r-sz2}});
			}
		}
		reverse(B.s.begin(), B.s.end());
	}

	printf("%d\n%d %d\n", ans.first, ans.second.first, ans.second.second);
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |      if(l+sz1-1 >= A.s.size() ||
      |         ~~~~~~~~^~~~~~~~~~~~~
necklace.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       r+sz1-1 >= B.s.size() ||
      |       ~~~~~~~~^~~~~~~~~~~~~
necklace.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      if(l+sz1+sz2-1 >= A.s.size() ||
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 57 ms 332 KB Output is correct
7 Partially correct 27 ms 332 KB Output is partially correct
8 Partially correct 50 ms 332 KB Output is partially correct
9 Correct 26 ms 332 KB Output is correct
10 Partially correct 5 ms 292 KB Output is partially correct
11 Correct 5 ms 304 KB Output is correct
12 Partially correct 34 ms 332 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 57 ms 332 KB Output is correct
7 Partially correct 27 ms 332 KB Output is partially correct
8 Partially correct 50 ms 332 KB Output is partially correct
9 Correct 26 ms 332 KB Output is correct
10 Partially correct 5 ms 292 KB Output is partially correct
11 Correct 5 ms 304 KB Output is correct
12 Partially correct 34 ms 332 KB Output is partially correct
13 Execution timed out 1537 ms 296 KB Time limit exceeded
14 Halted 0 ms 0 KB -