Submission #7529404


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

const ll p1 = 31, m1 = 1e9 + 7, p2 = 29, m2 = 1e9 + 9;
ll p11[300000], p22[300000];

struct Hash
{
	ll h1, h2;
	Hash() {}
	Hash(const ll& _h1, const ll& _h2)
	{
		h1 = _h1;
		h2 = _h2;
	}
	bool operator ==(const Hash& a) const
	{
		return (h1 == a.h1 && h2 == a.h2);
	}
	void operator +=(const Hash& a)
	{
		h1 += a.h1;
		h2 += a.h2;
		if (h1 >= m1)
			h1 -= m1;
		if (h2 >= m2)
			h2 -= m2;
	}
	void operator -=(const Hash& a)
	{
		h1 -= a.h1;
		h2 -= a.h2;
		if (h1 < 0)
			h1 += m1;
		if (h2 < 0)
			h2 += m2;
	}
	void operator *=(const int& x)
	{
		h1 *= p11[x];
		if (h1 >= m1)
			h1 %= m1;
		h2 *= p22[x];
		if (h2 >= m2)
			h2 %= m2;
	}
	Hash operator +(const Hash& a)const
	{
		ll x = h1 + a.h1, y = h2 + a.h2;
		if (x >= m1)
			x -= m1;
		if (y >= m2)
			y -= m2;
		return Hash(x, y);
	}
	Hash operator *(const int& z)const
	{
		ll x = h1 * p11[z], y = h2 * p22[z];
		if (x >= m1)
			x %= m1;
		if (y >= m2)
			y %= m2;
		return Hash(x, y);
	}
	Hash operator -(const Hash& a)const
	{
		ll x = h1 - a.h1, y = h2 - a.h2;
		if (x < 0)
			x += m1;
		if (y < 0)
			y += m2;
		return Hash(x, y);
	}
};

bool operator <(const Hash& a, const Hash& b)
{
	if (a.h1 != b.h1)
		return a.h1 < b.h1;
	return a.h2 < b.h2;
}

int n;
string s;
vector <Hash> h;

void calc_hashes(const string& s, vector <Hash>& a)
{
	a[0] = Hash(s[0] - 'a' + 1, s[0] - 'a' + 1);
	for (int i = 1; i < n; i++)
		a[i] = (a[i - 1] * 1) + Hash(s[i] - 'a' + 1, s[i] - 'a' + 1);
}

Hash Hash_otr(int l, int r)
{
	if (l == 0)
		return h[r];
	return h[r] - (h[l - 1] * (r - l + 1));
}

bool ch(int len)
{
	multiset <Hash> s;
	for (int i = len; i + len - 1 < n; i++)
		s.insert(Hash_otr(i, i + len - 1));
	for (int i = 0; i + len - 1 < n; i++)
	{
		Hash sos = Hash_otr(i, i + len - 1);
		if (s.find(sos) != s.end())
			return true; 
		if (!s.empty())
			s.erase(s.find(Hash_otr(len + i, len + i + len - 1)));
	}
	return false;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
	//freopen("rps2.in", "r", stdin);
	//freopen("rps2.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	p11[0] = p22[0] = 1;
	for (int i = 1; i < 300000; i++)
	{
		p11[i] = p1 * p11[i - 1];
		if (p11[i] >= m1)
			p11[i] %= m1;
		p22[i] = p2 * p22[i - 1];
		if (p22[i] >= m2)
			p22[i] %= m2;
	}
	cin >> n >> s;
	h.resize(n);
	calc_hashes(s, h);
	int l = 0, r = n;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		if (ch(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
	return 0;
}

Submission Info

Submission Time
Task E - Who Says a Pun?
User SHAMPINION
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3452 Byte
Status AC
Exec Time 24 ms
Memory 5376 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 70
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 01-handmade-12, 02-binary-13, 02-binary-14, 02-binary-15, 02-binary-16, 02-binary-17, 02-binary-18, 02-binary-19, 02-binary-20, 02-binary-21, 02-binary-22, 02-binary-23, 03-BigRandom-24, 03-BigRandom-25, 03-BigRandom-26, 03-BigRandom-27, 03-BigRandom-28, 03-BigRandom-29, 03-BigRandom-30, 03-BigRandom-31, 03-BigRandom-32, 03-BigRandom-33, 03-BigRandom-34, 03-BigRandom-35, 03-BigRandom-36, 03-BigRandom-37, 03-BigRandom-38, 03-BigRandom-39, 03-BigRandom-40, 03-BigRandom-41, 03-BigRandom-42, 03-BigRandom-43, 03-BigRandom-44, 03-BigRandom-45, 03-BigRandom-46, 03-BigRandom-47, 03-BigRandom-48, 03-BigRandom-49, 03-BigRandom-50, 03-BigRandom-51, 03-BigRandom-52, 03-BigRandom-53, 03-BigRandom-54, 04-zero-55, 04-zero-56, 05-AllRandom-57, 05-AllRandom-58, 05-AllRandom-59, 05-AllRandom-60, 05-AllRandom-61, 05-AllRandom-62, 05-AllRandom-63, 05-AllRandom-64, 05-AllRandom-65, 05-AllRandom-66, 05-AllRandom-67, 05-AllRandom-68, 05-AllRandom-69
Case Name Status Exec Time Memory
00-sample-00 AC 5 ms 4992 KB
00-sample-01 AC 5 ms 4992 KB
00-sample-02 AC 5 ms 4992 KB
01-handmade-03 AC 6 ms 4992 KB
01-handmade-04 AC 10 ms 5248 KB
01-handmade-05 AC 6 ms 4992 KB
01-handmade-06 AC 5 ms 4992 KB
01-handmade-07 AC 6 ms 5248 KB
01-handmade-08 AC 6 ms 4992 KB
01-handmade-09 AC 20 ms 5376 KB
01-handmade-10 AC 20 ms 5376 KB
01-handmade-11 AC 9 ms 5248 KB
01-handmade-12 AC 8 ms 5248 KB
02-binary-13 AC 18 ms 5248 KB
02-binary-14 AC 20 ms 5248 KB
02-binary-15 AC 17 ms 5248 KB
02-binary-16 AC 22 ms 5376 KB
02-binary-17 AC 21 ms 5376 KB
02-binary-18 AC 20 ms 5248 KB
02-binary-19 AC 15 ms 5248 KB
02-binary-20 AC 16 ms 5248 KB
02-binary-21 AC 16 ms 5248 KB
02-binary-22 AC 16 ms 5248 KB
02-binary-23 AC 15 ms 5248 KB
03-BigRandom-24 AC 6 ms 5120 KB
03-BigRandom-25 AC 6 ms 5120 KB
03-BigRandom-26 AC 8 ms 5120 KB
03-BigRandom-27 AC 9 ms 5248 KB
03-BigRandom-28 AC 11 ms 5248 KB
03-BigRandom-29 AC 9 ms 5248 KB
03-BigRandom-30 AC 12 ms 5144 KB
03-BigRandom-31 AC 8 ms 5144 KB
03-BigRandom-32 AC 10 ms 5248 KB
03-BigRandom-33 AC 11 ms 5120 KB
03-BigRandom-34 AC 6 ms 5248 KB
03-BigRandom-35 AC 10 ms 5120 KB
03-BigRandom-36 AC 8 ms 5248 KB
03-BigRandom-37 AC 7 ms 5144 KB
03-BigRandom-38 AC 7 ms 5120 KB
03-BigRandom-39 AC 6 ms 5248 KB
03-BigRandom-40 AC 10 ms 5148 KB
03-BigRandom-41 AC 7 ms 5248 KB
03-BigRandom-42 AC 7 ms 5248 KB
03-BigRandom-43 AC 7 ms 5120 KB
03-BigRandom-44 AC 9 ms 5148 KB
03-BigRandom-45 AC 11 ms 5248 KB
03-BigRandom-46 AC 10 ms 5120 KB
03-BigRandom-47 AC 10 ms 5248 KB
03-BigRandom-48 AC 7 ms 5148 KB
03-BigRandom-49 AC 8 ms 5120 KB
03-BigRandom-50 AC 9 ms 5248 KB
03-BigRandom-51 AC 6 ms 5248 KB
03-BigRandom-52 AC 9 ms 5248 KB
03-BigRandom-53 AC 9 ms 5248 KB
03-BigRandom-54 AC 7 ms 5248 KB
04-zero-55 AC 5 ms 4992 KB
04-zero-56 AC 5 ms 4992 KB
05-AllRandom-57 AC 23 ms 5376 KB
05-AllRandom-58 AC 22 ms 5376 KB
05-AllRandom-59 AC 22 ms 5376 KB
05-AllRandom-60 AC 22 ms 5376 KB
05-AllRandom-61 AC 22 ms 5376 KB
05-AllRandom-62 AC 23 ms 5376 KB
05-AllRandom-63 AC 23 ms 5376 KB
05-AllRandom-64 AC 22 ms 5376 KB
05-AllRandom-65 AC 23 ms 5376 KB
05-AllRandom-66 AC 22 ms 5376 KB
05-AllRandom-67 AC 22 ms 5376 KB
05-AllRandom-68 AC 24 ms 5376 KB
05-AllRandom-69 AC 23 ms 5376 KB