Submission #2166832

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)

template <typename Tp> void in(Tp &x) {
	char ch = getchar(), f = 1; x = 0;
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') ch = getchar(), f = -1;
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

template <typename Tp> void out(Tp x) {
	if (x > 9) out(x / 10);
	putchar(x % 10 + '0');
	return;
}

template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}
template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}

const int MAXN = 100010;

int n, A[MAXN];
int tot[MAXN];

void wa()
{
	puts("No"); exit(0);
}

int main()
{
	in(n); FOR(i, 1, n) in(A[i]);

	int pos = -1;
	FOR(i, 2, n) if (A[i] != A[1]) pos = i;

	if (pos != -1) {
		if (A[pos] != A[1] + 1 && A[pos] != A[1] - 1) wa();
		FOR(i, pos + 1, n) if (A[i] != A[pos] && A[i] != A[1]) wa();
	}

	if (pos == -1) {
		if (A[1] + 1 != n) {
			if (A[1] * 2 > n) wa();
		}
	}
	else {
		int all = 0;
		if (A[pos] == A[1] + 1) all = A[pos];
		else all = A[1];

		int tot = 0;
		FOR(i, 1, n) if (A[i] == all - 1) tot++;
		if ((all - tot) * 2 + tot > n || n - tot < 2 || tot >= all - 1) wa();
	}

	puts("Yes");
	
	return 0;
}

Submission Info

Judge Result