oj.uz

Submission #435597

# Submission time Handle Problem Language Result Execution time Memory
435597 2021-06-23T13:09:24 Z Sohsoh84 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 154 ms 11144 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 = 400 + 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 3 ms 2252 KB Output is correct
2 Correct 5 ms 2252 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 5 ms 2252 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 96 ms 8032 KB Output is correct
7 Correct 99 ms 8004 KB Output is correct
8 Correct 95 ms 7492 KB Output is correct
9 Correct 107 ms 7792 KB Output is correct
10 Correct 154 ms 7876 KB Output is correct
11 Correct 113 ms 7856 KB Output is correct
12 Correct 140 ms 7652 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 5 ms 2252 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 4 ms 2124 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 96 ms 8032 KB Output is correct
7 Correct 99 ms 8004 KB Output is correct
8 Correct 95 ms 7492 KB Output is correct
9 Correct 107 ms 7792 KB Output is correct
10 Correct 154 ms 7876 KB Output is correct
11 Correct 113 ms 7856 KB Output is correct
12 Correct 140 ms 7652 KB Output is correct
13 Runtime error 64 ms 11144 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -