oj.uz

Submission #435596

# Submission time Handle Problem Language Result Execution time Memory
435596 2021-06-23T13:03:47 Z Sohsoh84 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 131 ms 11140 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][R2], 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
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 5 ms 2124 KB Output is correct
5 Partially correct 4 ms 2124 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 5 ms 2124 KB Output is correct
5 Partially correct 4 ms 2124 KB Output is partially correct
6 Correct 96 ms 8044 KB Output is correct
7 Partially correct 98 ms 7956 KB Output is partially correct
8 Correct 84 ms 7492 KB Output is correct
9 Partially correct 101 ms 7748 KB Output is partially correct
10 Correct 113 ms 7976 KB Output is correct
11 Correct 131 ms 7948 KB Output is correct
12 Partially correct 99 ms 7784 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 5 ms 2124 KB Output is correct
5 Partially correct 4 ms 2124 KB Output is partially correct
6 Correct 96 ms 8044 KB Output is correct
7 Partially correct 98 ms 7956 KB Output is partially correct
8 Correct 84 ms 7492 KB Output is correct
9 Partially correct 101 ms 7748 KB Output is partially correct
10 Correct 113 ms 7976 KB Output is correct
11 Correct 131 ms 7948 KB Output is correct
12 Partially correct 99 ms 7784 KB Output is partially correct
13 Runtime error 40 ms 11140 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -