oj.uz

Submission #435599

# Submission time Handle Problem Language Result Execution time Memory
435599 2021-06-23T13:10:12 Z Sohsoh84 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 47200 KB 
// ¯\_(ツ)_/¯
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 3000 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll p, p_pow[MAXN], hsh[4][MAXN][MAXN], cyc_hsh[4][MAXN][MAXN];
string s1, s1_r, s2;

ll CycHash(int ind, int L, int R) {
	ll ans = 0;
	for (int i = L; i <= R; i++) {
		ll h = (hsh[ind][i + 1][R] + hsh[ind][L][i] * p_pow[R - i]) % MOD;
		ans ^= h;
	}

	return ans;
}


void RollHash(string s, int ind) {	
	int n = s.size();
	for (int L = 1; L <= n; L++) {
		for (int R = L; R <= n; R++) {
			int x = (s[R - 1] - 'a');
			hsh[ind][L][R] = (hsh[ind][L][R - 1] + p_pow[R - L] * x) % MOD;
		}
	}

	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
		       cyc_hsh[ind][i][j] = CycHash(ind, i, j);	
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s1 >> s2;
	s1_r = s1;
	reverse(all(s1_r));

	p = rng() % MOD;
	p_pow[0] = 1;
	for (int i = 1; i < MAXN; i++) p_pow[i] = p_pow[i - 1] * p % MOD;

	RollHash(s1, 0);
	RollHash(s1_r, 1);
	RollHash(s2, 2);
	
	for (int i = min(s1.size(), s2.size()); i > 0; i--) {
		for (int L1 = 1; L1 <= s1.size() - i + 1; L1++) {
			for (int L2 = 1; L2 <= s2.size() - i + 1; L2++) {
				int R1 = L1 + i - 1, R2 = L2 + i - 1, n = s1.size();
				ll hsh = cyc_hsh[2][L2][R2];
			       	ll hsh1 = cyc_hsh[0][L1][R1], hsh2 = cyc_hsh[1][n - R1 + 1][n - L1 + 1];
				if (hsh == hsh1 || hsh == hsh2) return cout << i << endl << L1 - 1 << sep << L2 - 1 << endl, 0;	
			}
		}
	}
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int L1 = 1; L1 <= s1.size() - i + 1; L1++) {
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
necklace.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for (int L2 = 1; L2 <= s2.size() - i + 1; L2++) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 4 ms 2976 KB Output is correct
3 Correct 3 ms 2508 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 4 ms 2976 KB Output is correct
3 Correct 3 ms 2508 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 132 ms 13732 KB Output is correct
7 Correct 108 ms 13744 KB Output is correct
8 Correct 122 ms 12680 KB Output is correct
9 Correct 117 ms 13264 KB Output is correct
10 Correct 136 ms 13652 KB Output is correct
11 Correct 127 ms 13520 KB Output is correct
12 Correct 113 ms 13084 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 4 ms 2976 KB Output is correct
3 Correct 3 ms 2508 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 132 ms 13732 KB Output is correct
7 Correct 108 ms 13744 KB Output is correct
8 Correct 122 ms 12680 KB Output is correct
9 Correct 117 ms 13264 KB Output is correct
10 Correct 136 ms 13652 KB Output is correct
11 Correct 127 ms 13520 KB Output is correct
12 Correct 113 ms 13084 KB Output is correct
13 Execution timed out 1588 ms 47200 KB Time limit exceeded
14 Halted 0 ms 0 KB -