oj.uz

Submission #469905

# Submission time Handle Problem Language Result Execution time Memory
469905 2021-09-02T09:07:32 Z naman1601 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 533 ms 71076 KB 
/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


void kmp(vector<int>& v, string s, int len) {

	fr(i, 1, len) {

		int j = v[i - 1];

		while(j > 0 && s[i] != s[j]) {

			j = v[j - 1];
		}

		if(s[i] == s[j]) {

			j++;
		}
		
		v[i] = j;
	}
}


const int maxn = 3005;
string s, t;
int sl, tl;
int stdp[maxn][maxn] = {0};
int tsdp[maxn][maxn] = {0};


int ans = 0;
pii ap = make_pair(-1, -1);


int inv(int idx) {

	return (sl - idx) - 1;
}


void pc() {

	fr(i, 0, sl) {

		string aux = s.substr(i, sl - i) + "#" + t;
		int al = aux.length();
		vector<int> pf(al, 0);
		kmp(pf, aux, al);

		fr(j, 0, tl) {

			stdp[i][j] = pf[al - tl + j];
		}
	}

	fr(i, 0, tl) {

		string aux = t.substr(i, tl - i) + "#" + s;
		int al = aux.length();
		vector<int> pf(al, 0);
		kmp(pf, aux, al);

		fr(j, 0, sl) {

			tsdp[i][j] = pf[al - sl + j];
		}
	}
}


void f() {

	fr(i, 0, 1) {

		fr(j, 0, tl) {

			int temp = stdp[i][j];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(0, j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}

	fr(i, 1, sl) {

		fr(j, 0, tl) {

			int temp = stdp[i][j] + tsdp[j + 1][i - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair((i - 1) - tsdp[j + 1][i - 1] + 1, j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}
}


void g() {

	fr(i, 0, 1) {

		fr(j, 0, tl) {

			int temp = stdp[i][j];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(inv(stdp[i][j] - 1), j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}

	fr(i, 1, sl) {

		fr(j, 0, tl) {

			int temp = stdp[i][j] + tsdp[j + 1][i - 1];

			if(temp > ans) {

				ans = temp;
				ap = make_pair(inv(i + stdp[i][j] - 1), j - stdp[i][j] + 1);
				// cout << ap.fe << " " << ap.se << " " << temp << nl;
			}
		}
	}
}


void solve() {

	cin >> s >> t;
	sl = s.length();
	tl = t.length();

	pc();

	// fr(i, 0, sl) {

	// 	fr(j, 0, tl) {

	// 		cout << i << ", " << j << ": " << stdp[i][j] << nl;
	// 	}
	// }

	f();
	reverse(s.begin(), s.end());
	pc();
	g();

	// fr(i, 0, sl) {

	// 	fr(j, 0, tl) {

	// 		cout << i << ", " << j << ": " << stdp[i][j] << nl;
	// 	}
	// }

	cout << ans << nl << ap.fe << " " << ap.se << nl;
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 9 ms 4824 KB Output is correct
7 Correct 8 ms 4800 KB Output is correct
8 Correct 8 ms 4300 KB Output is correct
9 Correct 8 ms 4684 KB Output is correct
10 Correct 9 ms 4788 KB Output is correct
11 Correct 9 ms 4740 KB Output is correct
12 Correct 8 ms 4556 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 9 ms 4824 KB Output is correct
7 Correct 8 ms 4800 KB Output is correct
8 Correct 8 ms 4300 KB Output is correct
9 Correct 8 ms 4684 KB Output is correct
10 Correct 9 ms 4788 KB Output is correct
11 Correct 9 ms 4740 KB Output is correct
12 Correct 8 ms 4556 KB Output is correct
13 Correct 489 ms 71076 KB Output is correct
14 Correct 457 ms 70976 KB Output is correct
15 Correct 533 ms 68780 KB Output is correct
16 Correct 454 ms 70408 KB Output is correct
17 Correct 389 ms 69692 KB Output is correct
18 Correct 404 ms 70800 KB Output is correct
19 Correct 414 ms 70596 KB Output is correct
20 Correct 445 ms 69644 KB Output is correct
21 Correct 467 ms 70084 KB Output is correct