fork(13) download
copy 
  1. #include <bits/stdc++.h>
  2. #define clr(x) memset((x), 0, sizeof(x))
  3. #define all(x) (x).begin(), (x).end()
  4. #define pb push_back
  5. #define mp make_pair
  6. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  7. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  8. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  9. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  10. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  11. #define in(x) int (x); input((x));
  12. #define x first
  13. #define y second
  14. #define less(a,b) ((a) < (b) - EPS)
  15. #define more(a,b) ((a) > (b) + EPS)
  16. #define eq(a,b) (fabs((a) - (b)) < EPS)
  17. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  18. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  19. using namespace std;
  20. typedef long double ld; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const ld EPS = 5e-12; char TEMPORARY_CHAR; typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(int a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[10]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  21.  
  22. #define bit(a, pos) ((a >> pos) & 1)
  23.  
  24. struct state
  25. {
  26.     int len;
  27. 	state * link;
  28. 	state * next[10];
  29. 	int cnt;
  30. 	char can;
  31. 	state()
  32. 	{
  33. 		cnt = 0;
  34. 		len = 0;
  35. 		link = 0;
  36. 		can = -1;
  37. 		memset(next, 0, sizeof(next));
  38. 	}
  39.  
  40. };
  41.  
  42. state * root;
  43. state * last;
  44.  
  45. void init_sa()
  46. {
  47. 	root = new state();
  48. 	last = root;
  49. }
  50.  
  51. vector <state *> pos[150001];
  52.  
  53. void extend_sa(int c)
  54. {
  55. 	state * cur = new state();
  56. 	cur->len = last->len + 1;
  57. 	pos[cur->len].pb(cur);
  58. 	cur->cnt = 1;
  59. 	state * p = last;
  60. 	for(; p && !p->next[c]; p = p->link)
  61. 		p->next[c] = cur;
  62. 	if (!p)
  63. 		cur->link = root;
  64. 	else
  65. 	{
  66. 		state * q = p->next[c];
  67. 		if (p->len + 1 == q->len)
  68. 			cur->link = q;
  69. 		else
  70. 		{
  71. 			state * clone = new state();
  72. 			clone->len = p->len + 1;
  73. 			pos[clone->len].pb(clone);
  74. 			memcpy(clone->next, q->next, sizeof(q->next));
  75. 			clone->link = q->link;
  76. 			for(; p && p->next[c] == q; p = p->link)
  77. 				p->next[c] = clone;
  78. 			q->link = cur->link = clone;
  79. 		}
  80. 	}
  81. 	last = cur;
  82. }
  83.  
  84. ll best = 0;
  85. state * bp;
  86.  
  87. char can(state * v)
  88. {
  89. 	if (!v) return 0;
  90. 	if (v->can != -1)
  91. 		return v->can;
  92. 	return v->can = can(v->link);
  93. }
  94.  
  95. int main()
  96. {
  97. 	in(n); in(m);
  98. 	int a[n];
  99. 	init_sa();
  100. 	forn(i, n)
  101. 	{
  102. 		a[i] = nxt() - 1;
  103. 		extend_sa(a[i]);
  104. 	}
  105. 	for(int i = n; i > 0; --i)
  106. 		for(int j = 0; j < (int)pos[i].size(); ++j)
  107. 		{
  108. 			state * x = pos[i][j];
  109. 			if (x->link) x->link->cnt += x->cnt;
  110. 			ll cur = x->len * 1LL * x->cnt;
  111. 			if (cur > best)
  112. 			{
  113. 				best = cur;
  114. 				bp = x;
  115. 			}
  116. 		}
  117. 	bp->can = 1;
  118. 	cout << best << endl;
  119. 	cout << bp->len << endl;
  120. 	state * cur = root;
  121. 	for(int i = 0; i < n; ++i)
  122. 	{
  123. 		cur = cur->next[a[i]];
  124. 		if (can(cur))
  125. 		{
  126. 			for(int j = 0; j < bp->len; ++j)
  127. 			{
  128. 				if (j) cout << " ";
  129. 				cout << a[i - bp->len + j + 1] + 1;
  130. 			}
  131. 			cout << endl;
  132. 			return 0;
  133. 		}
  134. 	}
  135. 	return 0;
  136.  
  137. }
  138.  
Time limit exceeded #stdin #stdout 5s 5056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6kM7l2
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!