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

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/status/GRSEQ,nikita_pletnev/

#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;
}