Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals

## 为什么无限WA啊，不是很明白

Posted by scallop at 2018-01-12 21:04:04 on Problem 1743
```#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int MAXN = 21000;
int n, m;
int a[MAXN], rank[MAXN], y[MAXN], sa[MAXN], w[MAXN], wv[MAXN];
int height[MAXN];

void buildSA()
{
m = 500;
memset(w, 0, sizeof w);
for (int i = 0; i < n; ++i)
{
rank[i] = a[i];
++w[a[i]];
}
for (int i = 1; i < m; ++i)
w[i] += w[i - 1];
for (int i = n - 1; i > -1; --i)
{
--w[a[i]];
sa[w[a[i]]] = i;
}
int p = 0;
for (int i = 1; i < n && p < n; i *= 2)
{
p = 0;
for (int j = n - i; j < n; ++j)
{
y[p] = j;
++p;
}
for (int j = 0; j < n; ++j)
{
if (sa[j] >= i)
{
y[p] = sa[j] - i;
++p;
}
}
for (int j = 0; j < n; ++j)
wv[j] = rank[y[j]];
memset(w, 0, sizeof w);
for (int j = 0; j < n; ++j)
++w[wv[j]];
for (int j = 1; j < m; ++j)
w[j] += w[j - 1];
for (int j = n - 1; j > -1; --j)
{
--w[wv[j]];
sa[w[wv[j]]] = y[j];
}
for (int j = 0; j < n; ++j)
swap(rank[j], y[j]);
rank[sa[0]] = 0;
p = 1;
for (int j = 1; j < n; ++j)
{
if (y[sa[j]] == y[sa[j - 1]] && y[sa[j] + i] == y[sa[j - 1] + i])
rank[sa[j]] = p - 1;
else
{
rank[sa[j]] = p;
++p;
}
}
m = p;
}
}

void calh()
{
for (int i = 0; i < n; ++i)
rank[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; height[rank[i++]] = k)
{
if (k > 0)
--k;
int j = sa[rank[i] - 1];
while (a[i + k] == a[j + k])
++k;
}
}

bool check(int x)
{
int big = sa[0], small = sa[0];
for (int i = 0; i < n; ++i)
{
if (height[i] >= x)
{
big = max(big, sa[i]);
small = min(small, sa[i]);
if (big - small > x)
return true;
}
else
{
big = sa[i];
small = sa[i];
}
}
if (big - small > x)
return true;
return false;
}

{
int x;
scanf("%d", &x);
return x;
}

int main()
{
//freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
while (true)
{
memset(a, 0, sizeof a);
memset(height, 0, sizeof height);
if (n == 0)
break;
for (int i = 0; i < n; ++i)
if (n < 10)
{
printf("0\n");
continue;
}
for (int i = 0; i < n; ++i)
a[i] = a[i] - a[i + 1];
--n;
a[n] = 0;
for (int i = 0; i < n; ++i)
a[i] += 180;
buildSA();
calh();
int beg = 1, end = n;
while (beg < end)
{
int mid = (beg + end + 1) / 2;
if (check(mid))
beg = mid;
else
end = mid - 1;
}
if (beg < 4)
printf("0\n");
else
printf("%d\n", beg + 1);
}
return 0;
}```

Followed by: