oj.uz

Submission #646428

# Submission time Handle Problem Language Result Execution time Memory
646428 2022-09-29T19:05:27 Z dozer Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 588 ms 4184 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
#define int long long

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, val3 = 0, val4 = 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()
{
	fastio();

	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 'std::pair<long long int, std::pair<long long int, long long int> > f(std::string, std::string)':
necklace.cpp:43:28: warning: unused variable 'val3' [-Wunused-variable]
   43 |    int val1 = 0, val2 = 0, val3 = 0, val4 = 0;
      |                            ^~~~
necklace.cpp:43:38: warning: unused variable 'val4' [-Wunused-variable]
   43 |    int val1 = 0, val2 = 0, val3 = 0, val4 = 0;
      |                                      ^~~~
necklace.cpp: In function 'int32_t main()':
necklace.cpp:118:20: warning: unused variable 'm' [-Wunused-variable]
  118 |  int n = s.size(), m = t.size();
      |                    ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1288 KB Output is correct
2 Correct 10 ms 1284 KB Output is correct
3 Correct 6 ms 1084 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 9 ms 1236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1288 KB Output is correct
2 Correct 10 ms 1284 KB Output is correct
3 Correct 6 ms 1084 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 9 ms 1236 KB Output is correct
6 Correct 588 ms 4120 KB Output is correct
7 Correct 562 ms 4140 KB Output is correct
8 Correct 425 ms 4068 KB Output is correct
9 Correct 529 ms 3988 KB Output is correct
10 Correct 546 ms 4076 KB Output is correct
11 Correct 524 ms 4184 KB Output is correct
12 Correct 498 ms 4000 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1288 KB Output is correct
2 Correct 10 ms 1284 KB Output is correct
3 Correct 6 ms 1084 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 9 ms 1236 KB Output is correct
6 Correct 588 ms 4120 KB Output is correct
7 Correct 562 ms 4140 KB Output is correct
8 Correct 425 ms 4068 KB Output is correct
9 Correct 529 ms 3988 KB Output is correct
10 Correct 546 ms 4076 KB Output is correct
11 Correct 524 ms 4184 KB Output is correct
12 Correct 498 ms 4000 KB Output is correct
13 Runtime error 1 ms 468 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -