13560번: Football

https://www.acmicpc.net/problem/13560


$O(n)$

https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets

#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[10000], s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", w + i);
    sort(w, w + n);
    for (int i = 0; i < n; i++) if ((s += w[i] - i) < 0) {
        puts("-1");
        return 0;
    }
    printf("%d", s ? -1 : 1);
    return 0;
}