Submission #7527178


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[100000], p22[100000];

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 m, 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 check(int l1, int r1, int l2, int r2)
{
	Hash a = Hash_otr(l1, r1), b = Hash_otr(l2, r2);
	return (a == b && r1 - l1 == r2 - l2);
}

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(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 < 100000; 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 0
Code Size 3590 Byte
Status WA
Exec Time 26 ms
Memory 2176 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 43
WA × 27
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 3 ms 1792 KB
00-sample-01 AC 3 ms 1792 KB
00-sample-02 AC 3 ms 1792 KB
01-handmade-03 AC 3 ms 1920 KB
01-handmade-04 WA 11 ms 2176 KB
01-handmade-05 AC 3 ms 1920 KB
01-handmade-06 AC 3 ms 1920 KB
01-handmade-07 AC 3 ms 2048 KB
01-handmade-08 AC 3 ms 1920 KB
01-handmade-09 AC 18 ms 2176 KB
01-handmade-10 AC 18 ms 2176 KB
01-handmade-11 AC 7 ms 2048 KB
01-handmade-12 AC 5 ms 2048 KB
02-binary-13 WA 15 ms 2176 KB
02-binary-14 WA 18 ms 2176 KB
02-binary-15 WA 14 ms 2176 KB
02-binary-16 WA 18 ms 2176 KB
02-binary-17 WA 19 ms 2176 KB
02-binary-18 WA 17 ms 2176 KB
02-binary-19 WA 14 ms 2048 KB
02-binary-20 WA 15 ms 2176 KB
02-binary-21 AC 14 ms 2048 KB
02-binary-22 WA 14 ms 2048 KB
02-binary-23 WA 14 ms 2048 KB
03-BigRandom-24 AC 4 ms 2048 KB
03-BigRandom-25 AC 4 ms 2048 KB
03-BigRandom-26 AC 5 ms 2048 KB
03-BigRandom-27 AC 6 ms 2048 KB
03-BigRandom-28 WA 19 ms 2176 KB
03-BigRandom-29 AC 7 ms 2048 KB
03-BigRandom-30 WA 20 ms 2176 KB
03-BigRandom-31 AC 5 ms 2048 KB
03-BigRandom-32 AC 8 ms 2048 KB
03-BigRandom-33 WA 18 ms 2176 KB
03-BigRandom-34 AC 4 ms 2048 KB
03-BigRandom-35 AC 8 ms 2048 KB
03-BigRandom-36 AC 6 ms 2048 KB
03-BigRandom-37 AC 4 ms 2048 KB
03-BigRandom-38 AC 5 ms 2048 KB
03-BigRandom-39 AC 4 ms 2048 KB
03-BigRandom-40 AC 8 ms 2048 KB
03-BigRandom-41 AC 5 ms 2048 KB
03-BigRandom-42 AC 4 ms 2048 KB
03-BigRandom-43 AC 4 ms 2048 KB
03-BigRandom-44 AC 6 ms 2048 KB
03-BigRandom-45 AC 8 ms 2048 KB
03-BigRandom-46 AC 7 ms 2048 KB
03-BigRandom-47 AC 7 ms 2048 KB
03-BigRandom-48 AC 4 ms 2048 KB
03-BigRandom-49 AC 6 ms 2048 KB
03-BigRandom-50 AC 7 ms 2048 KB
03-BigRandom-51 AC 4 ms 2048 KB
03-BigRandom-52 AC 6 ms 2048 KB
03-BigRandom-53 AC 6 ms 2048 KB
03-BigRandom-54 AC 5 ms 2048 KB
04-zero-55 AC 3 ms 1792 KB
04-zero-56 AC 3 ms 1792 KB
05-AllRandom-57 WA 21 ms 2176 KB
05-AllRandom-58 WA 20 ms 2176 KB
05-AllRandom-59 WA 21 ms 2176 KB
05-AllRandom-60 WA 26 ms 2176 KB
05-AllRandom-61 WA 20 ms 2176 KB
05-AllRandom-62 WA 21 ms 2176 KB
05-AllRandom-63 WA 21 ms 2176 KB
05-AllRandom-64 WA 21 ms 2176 KB
05-AllRandom-65 WA 21 ms 2176 KB
05-AllRandom-66 WA 21 ms 2176 KB
05-AllRandom-67 WA 21 ms 2176 KB
05-AllRandom-68 WA 21 ms 2176 KB
05-AllRandom-69 WA 20 ms 2176 KB