oj.uz

Submission #501540

# Submission time Handle Problem Language Result Execution time Memory
501540 2022-01-03T20:01:00 Z Arnch Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 436 ms 165708 KB 
// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long long ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 3e3 + 10, mod = 1e9 + 7, pr = 1000696969;

string s, t;
string st[2][N];

int n, m;
int f[2][N][N * 2];

void calc_f(int x, int y) {
	f[x][y][0] = 0;
	int k = 0;
	
	for(int i = 1; i < Sz(st[x][y]); i++) {
		while(k && st[x][y][k] != st[x][y][i]) 
			k = f[x][y][k - 1];

		k += (st[x][y][k] == st[x][y][i]);
		f[x][y][i] = k;
	}
}


int main() {
    fast_io;
	
	cin >>s >>t;
	n = Sz(s), m = Sz(t);
	
	st[0][n] = st[1][m] = "";
	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = s[i] + st[0][i + 1];
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = t[i] + st[1][i + 1];

	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = st[0][i] + '#' + t;
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = st[1][i] + '#' + s;

	for(int i = 0; i < n; i++)
		calc_f(0, i);
	for(int i = 0; i < m; i++)
		calc_f(1, i);	

		
	int ans = 0, pos1 = 0, pos2 = 0;
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			int val = f[1][i][j + m - i + 1];
			if(j < n - 1 && i > 0 && n - j + i - 1 < m + n - j)
				val += f[0][j + 1][n - j + i - 1];


			ans = max(ans, val);
			if(ans == val) {
				pos1 = j - f[1][i][j + m - i + 1] + 1;
				pos2 = i - f[0][j + 1][n - j + i - 1];
			}
		}
	}

	reverse(all(t));


	st[0][n] = st[1][m] = "";
	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = s[i] + st[0][i + 1];
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = t[i] + st[1][i + 1];

	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = st[0][i] + '#' + t;
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = st[1][i] + '#' + s;

	for(int i = 0; i < n; i++)
		calc_f(0, i);
	for(int i = 0; i < m; i++)
		calc_f(1, i);	

		
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			int val = f[1][i][j + m - i + 1];
			if(j < n - 1 && i > 0 && n - j + i - 1 < m + n - j)
				val += f[0][j + 1][n - j + i - 1];


			ans = max(ans, val);
			if(ans == val) {
				pos1 = j - f[1][i][j + m - i + 1] + 1;
				pos2 = (m - (i - f[0][j + 1][n - j + i - 1])) - val;
			}
		}
	}

	cout<<ans <<endl <<pos1 <<" " <<pos2 <<endl;

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 8 ms 6368 KB Output is correct
7 Correct 6 ms 6348 KB Output is correct
8 Correct 6 ms 5580 KB Output is correct
9 Correct 6 ms 6136 KB Output is correct
10 Correct 6 ms 6228 KB Output is correct
11 Correct 6 ms 6220 KB Output is correct
12 Correct 8 ms 5964 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 8 ms 6368 KB Output is correct
7 Correct 6 ms 6348 KB Output is correct
8 Correct 6 ms 5580 KB Output is correct
9 Correct 6 ms 6136 KB Output is correct
10 Correct 6 ms 6228 KB Output is correct
11 Correct 6 ms 6220 KB Output is correct
12 Correct 8 ms 5964 KB Output is correct
13 Correct 405 ms 165708 KB Output is correct
14 Correct 351 ms 165656 KB Output is correct
15 Correct 436 ms 157688 KB Output is correct
16 Correct 339 ms 163188 KB Output is correct
17 Correct 306 ms 161064 KB Output is correct
18 Correct 331 ms 164960 KB Output is correct
19 Correct 337 ms 164244 KB Output is correct
20 Correct 357 ms 160528 KB Output is correct
21 Correct 374 ms 162004 KB Output is correct