# Участник:Никита Плетнев/spoj graphic sequence

Перейти к: навигация, поиск
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(long deg1, long deg2) {
return deg1 > deg2;
}

vector<long> cumulative_sum(vector<long> & d) {
vector<long> cum(d.size() + 1, 0);
for (long i = 0; i < d.size(); ++i) {
cum[i + 1] = cum[i] + d[i];
}
return cum;
}

vector<long> start_leq(vector<long> & d) {
long n = d.size();
vector<long> leq(n + 1, -1);
for (long i = 0; i < n; ++i) {
long deg = d[i] + 1;
if (leq[deg] == -1)
leq[deg] = i;
}
long curr = -1;
for (long i = 0; i <= n; ++i) {
if (leq[i] == -1)
leq[i] = curr;
else
curr = leq[i];
}
return leq;
}

bool is_graphic(vector<long> & degrees) {
long n = degrees.size();
sort(degrees.begin(), degrees.end(), cmp);
if (degrees[0] >= n)
return false;
vector<long> D = cumulative_sum(degrees);
if (D[n] % 2 == 1)
return false;
vector<long> M = start_leq(degrees);
for (long k = 1; k < n; ++k) {
if (M[k] > k) {
if (D[k] > k * M[k] - k + D[n] - D[M[k]])
return false;
} else {
if (D[k] * 2 > D[n] + k * (k - 1))
return false;
}
}
return true;
}

int main() {
long n_req;
cin >> n_req;
vector<bool> ans(n_req, false);
for (long i = 0; i < n_req; ++i) {
long n_vert;
cin >> n_vert;
vector<long> degrees(n_vert, 0);
for (long j = 0; j < n_vert; ++j) {
cin >> degrees[j];
}
ans[i] = is_graphic(degrees);
}
for (long i = 0; i < n_req; ++i) {
if (ans[i])
cout << "POSSIBLE\n";
else
cout << "IMPOSSIBLE\n";
}
return 0;
}
```