oj.uz

Submission #646427

# Submission time Handle Problem Language Result Execution time Memory
646427 2022-09-29T19:03:50 Z dozer Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 566 ms 2312 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 405

int rev1[N][N], rev2[N][N], dp[N][N], e1[N], e2[N];
const int mod1 = 1e9 + 7, mod2 = 1e9 + 37, p1 = 37, p2 = 31;

inline int add(int a, int b, int m)
{
	if (a + b < m) return a + b;
	return a + b - m;
}

inline int subs(int a, int b, int m)
{
	if (a >= b) return a - b;
	return a - b + m;
}

inline int mul(int a, int b, int m)
{
	return (a * b) % m;
}


pair<int, pii> f(string s, string t)
{
	int n = s.size(), m = t.size();
	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j <= m; j++)
		{
			int x = i, y = j;
			int val1 = 0, val2 = 0;
			rev1[i][j] = 0;
			while(x > 0 && y <= m)
			{
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, s[x - 1] - 'a' + 1, mod1);
				val2 = add(val2, mul(t[y - 1] - 'a' + 1, e1[y - j], mod1), mod1);
				if (val1 == val2) rev1[i][j] = y - j + 1;
				y++, x--;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= 1; j--)
		{
			int x = i, y = j;
			int val1 = 0, val2 = 0;
			rev2[i][j] = 0;
			while(x <= n && y > 0)
			{
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, t[y - 1] - 'a' + 1, mod1);
				val2 = add(val2, mul(s[x - 1] - 'a' + 1, e1[x - i], mod1), mod1);
				if (val1 == val2) rev2[i][j] = x - i + 1;
				y--, x++;
			}
		}
	}

	for (int i = n; i >= 1; i--)
	{
		for (int j = m; j >= 1; j--)
		{
			if (s[i - 1] != t[j - 1])
			{
				dp[i][j] = 0;
				continue;
			}
			dp[i][j] = dp[i + 1][j + 1] + 1;
		}
	}

	int ans = 0, x = 0, y = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int l = dp[i][j];
			int t1 = dp[i][j] + rev2[i + l][j - 1];
			int t2 = dp[i][j] + rev1[i - 1][j + l];
			if (t1 > ans)
			{
				ans = t1;
				x = i, y = j - rev2[i + l][j - 1];
			}
			if (t2 > ans)
			{
				ans = t2;
				x = i - rev1[i - 1][j + l], y = j;
			}
		}
	}

	return {ans, {x - 1, y - 1}};
}

int32_t main()
{

	string s, t;
	cin>>s>>t;

	int n = s.size(), m = t.size();

	e1[0] = 1, e2[0] = 1;
	for (int i = 1; i < N; i++)
		e1[i] = mul(e1[i - 1], p1, mod1), e2[i] = mul(e2[i - 1], p2, mod2);

	pair<int, pii> tmp = f(s, t);
	
	reverse(s.begin(), s.end());
	pair<int, pii> tmp2 = f(s, t);
	if (tmp.st < tmp2.st)
	{
		int l = tmp2.st;
		tmp.st = l;
		tmp.nd.st = (n - 1) - tmp2.nd.st - l + 1;
		tmp.nd.nd = tmp2.nd.nd;	
	}
	cout<<tmp.st<<endl;
	cout<<tmp.nd.st<<sp<<tmp.nd.nd<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

Compilation message

necklace.cpp: In function 'int32_t main()':
necklace.cpp:116:20: warning: unused variable 'm' [-Wunused-variable]
  116 |  int n = s.size(), m = t.size();
      |                    ^

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Partially correct 9 ms 724 KB Output is partially correct
3 Correct 7 ms 596 KB Output is correct
4 Partially correct 7 ms 792 KB Output is partially correct
5 Correct 9 ms 724 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Partially correct 9 ms 724 KB Output is partially correct
3 Correct 7 ms 596 KB Output is correct
4 Partially correct 7 ms 792 KB Output is partially correct
5 Correct 9 ms 724 KB Output is correct
6 Partially correct 543 ms 2204 KB Output is partially correct
7 Partially correct 566 ms 2312 KB Output is partially correct
8 Correct 407 ms 2280 KB Output is correct
9 Correct 514 ms 2120 KB Output is correct
10 Partially correct 536 ms 2188 KB Output is partially correct
11 Partially correct 537 ms 2184 KB Output is partially correct
12 Partially correct 481 ms 2136 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Partially correct 9 ms 724 KB Output is partially correct
3 Correct 7 ms 596 KB Output is correct
4 Partially correct 7 ms 792 KB Output is partially correct
5 Correct 9 ms 724 KB Output is correct
6 Partially correct 543 ms 2204 KB Output is partially correct
7 Partially correct 566 ms 2312 KB Output is partially correct
8 Correct 407 ms 2280 KB Output is correct
9 Correct 514 ms 2120 KB Output is correct
10 Partially correct 536 ms 2188 KB Output is partially correct
11 Partially correct 537 ms 2184 KB Output is partially correct
12 Partially correct 481 ms 2136 KB Output is partially correct
13 Runtime error 1 ms 468 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -