oj.uz

Submission #873053

# Submission time Handle Problem Language Result Execution time Memory
873053 2023-11-14T11:35:35 Z Trisanu_Das Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 66 ms 11100 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:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int L1 = 1; L1 <= s1.size() - i + 1; L1++) {
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
necklace.cpp:64:24: 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 L2 = 1; L2 <= s2.size() - i + 1; L2++) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 2 ms 5716 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5444 KB Output is correct
5 Correct 2 ms 5704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 2 ms 5716 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5444 KB Output is correct
5 Correct 2 ms 5704 KB Output is correct
6 Correct 58 ms 9840 KB Output is correct
7 Correct 58 ms 9592 KB Output is correct
8 Correct 52 ms 8268 KB Output is correct
9 Correct 66 ms 9812 KB Output is correct
10 Correct 65 ms 8556 KB Output is correct
11 Correct 66 ms 8528 KB Output is correct
12 Correct 58 ms 8272 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5468 KB Output is correct
2 Correct 2 ms 5716 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 2 ms 5444 KB Output is correct
5 Correct 2 ms 5704 KB Output is correct
6 Correct 58 ms 9840 KB Output is correct
7 Correct 58 ms 9592 KB Output is correct
8 Correct 52 ms 8268 KB Output is correct
9 Correct 66 ms 9812 KB Output is correct
10 Correct 65 ms 8556 KB Output is correct
11 Correct 66 ms 8528 KB Output is correct
12 Correct 58 ms 8272 KB Output is correct
13 Runtime error 26 ms 11100 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -