oj.uz

Submission #501539

# Submission time Handle Problem Language Result Execution time Memory
501539 2022-01-03T19:59:30 Z Arnch Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 7 ms 6332 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 = 2e3 + 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 1356 KB Output is correct
2 Correct 1 ms 1336 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 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 1356 KB Output is correct
2 Correct 1 ms 1336 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 7 ms 6332 KB Output is correct
7 Correct 5 ms 6220 KB Output is correct
8 Correct 6 ms 5452 KB Output is correct
9 Correct 6 ms 6092 KB Output is correct
10 Correct 5 ms 6220 KB Output is correct
11 Correct 7 ms 6172 KB Output is correct
12 Correct 6 ms 5964 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1336 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 7 ms 6332 KB Output is correct
7 Correct 5 ms 6220 KB Output is correct
8 Correct 6 ms 5452 KB Output is correct
9 Correct 6 ms 6092 KB Output is correct
10 Correct 5 ms 6220 KB Output is correct
11 Correct 7 ms 6172 KB Output is correct
12 Correct 6 ms 5964 KB Output is correct
13 Runtime error 2 ms 688 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -