Submission #906249

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
#ifdef LOCAL
    ifstream cin("input.txt");
    ofstream cout("output.txt");
#else
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#endif // LOCAL

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> cnt(n + 1, 0);
    int diam = 0;
    for (int i = 0;i < n; ++i)
    {
        if (a[i] > diam)
            diam = a[i];
        ++cnt[a[i]];
    }
    bool possible = true;
    for (int i = diam / 2 + 1; i <= diam; ++i)
    {
        if (cnt[i] < 2)
            possible = false;
    }
    int top = diam / 2 + diam % 2;
    if (diam % 2 == 0 && cnt[top] != 1)
    {
        possible = false;
    }
    if (diam % 2 == 1 && cnt[top] != 2)
        possible = false;
    for (int i = 0; i < top; ++i)
    {
        if (cnt[i] != 0)
        {
            possible = false;
            break;
        }
    }
    if (possible)
    {
        cout << "Possible\n";
    }
    else
    {
        cout << "Impossible\n";
    }

#ifdef LOCAL
    cin.close();
    cout.close();
#endif // LOCAL
    return 0;
}

Submission Info

Judge Result