#448302 (C++14) No.4 おもりと天秤

提出ソース

結果

問題	No.4 おもりと天秤
ユーザー	alexara1123
提出日時	2020-03-23 11:15:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5 ms / 5,000 ms
コード長	30,789 bytes
コンパイル時間	1,937 ms
コンパイル使用メモリ	145,732 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-07 20:41:18
合計ジャッジ時間	2,737 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	3 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	5 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	5 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	4 ms 6,940 KB
testcase_10	AC	5 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	5 ms 6,940 KB
testcase_19	AC	5 ms 6,944 KB
testcase_20	AC	4 ms 6,940 KB
testcase_21	AC	5 ms 6,940 KB
testcase_22	AC	5 ms 6,940 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'll bfs(ll, ll, std::vector<std::vector<std::pair<long long int, long long int> > >)':
main.cpp:718:1: warning: no return statement in function returning non-void [-Wreturn-type]
  718 | }
      | ^

ソースコード

raw source code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <numeric>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, ll> PL;
const ll mod = 1000000007;
// const ll mod = 998244353;
const ll MOD = 1000000007;
const ll INF = 1LL << 60;
#define PI (acos(-1))
#define ALL(c) (c).begin(), (c).end()
#define en '\n'
#define endl '\n'

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (auto &v : vec)
        is >> v;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    os << "[";
    for (auto v : vec)
        os << v << ",";
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec)
{
    os << "deq[";
    for (auto v : vec)
        os << v << ",";
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec)
{
    os << "{";
    for (auto v : vec)
        os << v << ",";
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec)
{
    os << "{";
    for (auto v : vec)
        os << v << ",";
    os << "}";
    return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{
    os << "(" << pa.first << "," << pa.second << ")";
    return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp)
{
    os << "{";
    for (auto v : mp)
        os << v.first << "=>" << v.second << ",";
    os << "}";
    return os;
}

#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
// template <typename A, size_t N, typename T>

template <typename T>
inline string toString(const T &a)
{
    ostringstream oss;
    oss << a;
    return oss.str();
};

template <int mod>
struct ModInt
{
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p)
    {
        if ((x += p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p)
    {
        if ((x += mod - p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p)
    {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p)
    {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const
    {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0)
        {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const
    {
        ModInt ret(1), mul(x);
        while (n > 0)
        {
            if (n & 1)
                ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p)
    {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a)
    {
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using modint = ModInt<mod>;

template <typename T>
struct Combination
{
    vector<T> _fact, _rfact, _inv;

    Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1)
    {
        _fact[0] = _rfact[sz] = _inv[0] = 1;
        for (int i = 1; i <= sz; i++)
            _fact[i] = _fact[i - 1] * i;
        _rfact[sz] /= _fact[sz];
        for (int i = sz - 1; i >= 0; i--)
            _rfact[i] = _rfact[i + 1] * (i + 1);
        for (int i = 1; i <= sz; i++)
            _inv[i] = _rfact[i] * _fact[i - 1];
    }

    inline T fact(int k) const { return _fact[k]; }

    inline T rfact(int k) const { return _rfact[k]; }

    inline T inv(int k) const { return _inv[k]; }

    T P(int n, int r) const
    {
        if (r < 0 || n < r)
            return 0;
        return fact(n) * rfact(n - r);
    }

    T C(int p, int q) const
    {
        if (q < 0 || p < q)
            return 0;
        return fact(p) * rfact(q) * rfact(p - q);
    }

    T H(int n, int r) const
    {
        if (n < 0 || r < 0)
            return (0);
        return r == 0 ? 1 : C(n + r - 1, r);
    }

    T NC(int p, int q) const
    {
        modint ret = 1;
        for (int i = 1; i <= q; i += 1)
        {
            ret = ret * p / i;
            p--;
        }
        return ret;
    }
};

// template <typename T>
// T binomial(ll N, ll K)
// {
//     if (K < 0 || N < K)
//         return 0;
//     T ret = 1;
//     for (int i = 1; i <= K; i++)
//     {

//         ret *= N--;
//         ret /= (modint)i;
//     }
//     return ret;
// }

template <typename T>
T binomial(ll N, ll K)
{
    if (K < 0 || N < K)
        return 0;
    T ret = 1;
    for (int i = 1; i <= K; i++)
    {

        ret *= N--;
        ret /= i;
    }
    return ret;
}
ll lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

bool is_prime(ll x)
{
    if (x == 1)
    {
        return false;
    }
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

map<ll, int> prime_factor(ll n)
{
    map<ll, int> ret;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

vector<ll> divisor(ll n)
{
    vector<ll> ret;
    for (ll i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

vector<bool> prime_table(int n)
{
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i)
        {
            prime[j] = false;
        }
    }
    return prime;
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod)
{
    return modpow(a, mod - 2, mod);
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x)
    {
        if (par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool issame(int x, int y)
    {
        return root(x) == root(y);
    }

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (par[x] > par[y])
            swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x)
    {
        return -par[root(x)];
    }
};

struct BIT
{
    //1-indexed!!!
    int n;
    vector<int> bit;
    BIT()
    {
        init();
    }
    BIT(int n) : n(n)
    {
        init();
    }
    void init()
    {
        bit.clear();
        bit.resize(n + 1, 0);
    }
    int sum(int i)
    {
        int s = 0;
        while (i > 0)
        {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    int sum(int x, int y)
    {
        return sum(y) - sum(x - 1);
    }
    void add(int i, int x)
    {
        while (i <= n)
        {
            bit[i] += x;
            i += i & -i;
        }
    }
    int lower_bound(int w)
    {
        if (w <= 0)
            return 0;
        int x = 0, r = 1;
        while (r < n)
            r <<= 1;
        for (int k = r; k > 0; k >>= 1)
        {
            if (x + k <= n && bit[x + k] < w)
            {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

struct LazySegmentTree
{
    // private:
    ll n;
    vector<ll> node, lazy;

    // public:
    LazySegmentTree(vector<ll> v)
    {
        int sz = (int)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }

    void eval(int k, int l, int r)
    {
        if (lazy[k] != 0)
        {
            node[k] += lazy[k];
            if (r - l > 1)
            {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else
        {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    ll getsum(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return 0;
        if (a <= l && r <= b)
            return node[k];
        ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
};

ll digit_sum(ll v)
{
    ll ret = 0;
    while (v)
    {
        ret += (v % 10);
        v /= 10;
    }
    return ret;
}

template <typename T>
struct Kruskal
{

    struct edge
    {
        ll from, to;
        T cost;
        ll used;
        edge() {}
        edge(ll from, ll to, T cost) : from(from), to(to), cost(cost), used(0) {}
        bool operator<(const edge &e) const
        {
            return cost < e.cost;
        }
    };

    ll n;
    vector<ll> p, r;
    vector<edge> edges;

    Kruskal() {}
    Kruskal(ll n) : n(n) {}

    void init(ll n)
    {
        r.assign(n, 1);
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    ll find(ll x)
    {
        return (x == p[x] ? x : p[x] = find(p[x]));
    }

    bool same(ll x, ll y)
    {
        return find(x) == find(y);
    }

    void unite(ll x, ll y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (r[x] < r[y])
            swap(x, y);
        r[x] += r[y];
        p[y] = x;
    }

    void add_edge(ll u, ll v, T c)
    {
        edges.emplace_back(u, v, c);
    }

    T build()
    {
        sort(edges.begin(), edges.end());
        init(n);
        T res = 0;
        for (auto &e : edges)
        {
            if (!same(e.from, e.to))
            {
                res += e.cost;
                unite(e.from, e.to);
                e.used = 1;
            }
        }
        return res;
    }

    T build(ll k)
    {
        sort(edges.begin(), edges.end());
        init(n);
        T res = 0;
        ll cnt = 0;
        for (auto &e : edges)
        {
            if (!same(e.from, e.to))
            {
                res += e.cost;
                unite(e.from, e.to);
                e.used = 1;
                cnt++;
            }
            if (cnt == k)
            {
                break;
            }
        }
        return res;
    }
};

int LIS(int a[], int n)
{
    vector<int> A(n, 0x3f3f3f3f);
    for (int i = 0; i < n; i++)
        *lower_bound(A.begin(), A.end(), a[i]) = a[i];
    return find(A.begin(), A.end(), 0x3f3f3f3f) - A.begin();
}

//  string maze[1010];
// //ll maze[100][100];
// ll grid_bfs(ll H, ll W, ll sx, ll sy, ll gx, ll gy)
// {
//     //O(E)

//     int dx[4] = {1, 0, -1, 0};
//     int dy[4] = {0, 1, 0, -1};

//     vector<vector<ll>> dist(H, vector<ll>(W, -1));
//     dist[sy][sx] = 0;

//     queue<PL> q;
//     q.push({sy, sx});
//     while (!q.empty())
//     {
//         ll x, y;
//         tie(y, x) = q.front();
//         q.pop();
//         if (y == gy && x == gx)
//         {
//             break;
//         }
//         for (int t = 0; t < 4; t++)
//         {
//             ll nx = x + dx[t], ny = y + dy[t];
//             if (nx < 0 || ny < 0 || nx >= W || ny >= H || dist[ny][nx] != -1 || maze[ny][nx] == '#')
//             {
//                 continue;
//             }

//             dist[ny][nx] = dist[y][x] + 1;
//             q.push({ny, nx});
//         }
//     }

//     return dist[gy][gx];
// }

// no verify
ll bfs(ll n, ll start, vector<vector<PL>> Edges)
{

    vector<ll> dist(n + 1, -1);
    dist[start] = 0;
    queue<PL> q;
    q.push({start, 0});

    while (!q.empty())
    {
        ll node, cost;
        tie(cost, node) = q.front();
        q.pop();
        for (auto p : Edges[node])
        {
            ll v = p.first, cost = p.second;
            if (dist[v] == -1)
            {
                dist[v] = dist[node] + cost;
                q.push({v, cost});
            }
        }
    }
}

vector<vector<ll>> warshall_floyd(ll n, vector<vector<ll>> g, ll INF)
{
    //init vector<vector<ll>> c(10,vector<ll>(10,0));

    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (g[i][k] == INF || g[k][j] == INF)
                    continue;
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    return g;
}

struct Dijkstra
{

    ll n;
    vector<vector<pair<ll, ll>>> Edges;
    vector<ll> Dist;
    vector<ll> Prev;
    vector<ll> PathNum;

    Dijkstra(ll n) : n(n), Edges(n), Dist(n), Prev(n), PathNum(n)
    {
        Prev.assign(n, -1);
    };

    void add_edge(ll a, ll b, ll c, bool directed = true)
    {
        if (directed)
        {
            Edges[a].emplace_back(make_pair(b, c));
        }
        else
        {
            Edges[a].emplace_back(make_pair(b, c));
            Edges[b].emplace_back(make_pair(a, c));
        }
    }
    // O((E+V)logV)
    void build(int start)
    {
        priority_queue<P, vector<P>, greater<P>> queue;
        fill(Dist.begin(), Dist.end(), 1e+18); //1e18 !?!?
        fill(Prev.begin(), Prev.end(), -1);    //1e18 !?!?
        Dist[start] = 0;
        PathNum[start] = 1;
        queue.push(PL(0, start));

        while (!queue.empty())
        {
            PL p = queue.top();
            queue.pop();
            int v = p.second;
            if (Dist[v] < p.first)
                continue;

            for (int i = 0; i < Edges[v].size(); i++)
            {
                PL e = Edges[v][i];
                if (Dist[e.first] > Dist[v] + e.second)
                {
                    Dist[e.first] = Dist[v] + e.second;
                    queue.push(P(Dist[e.first], e.first));

                    Prev[e.first] = v;

                    PathNum[e.first] = PathNum[v];
                }
                else if (Dist[e.first] == Dist[v] + e.second)
                {
                    PathNum[e.first] += PathNum[v];
                    PathNum[e.first] %= MOD;
                }
            }
        }
    }

    ll dist(ll t)
    {
        return Dist[t];
    }

    vector<ll> get_path(ll t)
    {
        vector<ll> path;
        for (; t != -1; t = Prev[t])
        {
            path.push_back(t);
        }
        reverse(path.begin(), path.end());
        return path;
    }

    ll get_path_num(ll t)
    {
        return PathNum[t];
    }

    // int solve()
    // {
    //    ll v, e, r;
    //    cin >> v >> e >> r;
    //    Dijkstra dij(v);
    //    for (int i = 0; i < e; i++)
    //    {
    //       ll a, b, c;
    //       cin >> a >> b >> c;
    //       dij.add_edge(a, b, c);
    //    }
    //    dij.build(r);
    //    for (int i = 0; i < v; i++)
    //    {
    //       if (dij.dist(i) == 1e18)
    //       {
    //          cout << "INF" << endl;
    //       }
    //       else
    //       {
    //          cout << dij.dist(i) << endl;
    //          cout << dij.get_path(i) << endl;
    //          cout << dij.get_path_num(i) << endl;
    //       }
    //    }
    //    return 0;
    // }
};



struct LCA
{
    int n, h;
    vector<vector<int>> par;
    vector<vector<pair<int, int>>> v;
    vector<ll> depth, dis;
    LCA(int sz) : n(sz), v(n), depth(n), dis(n)
    {
        h = 1;
        while ((1 << h) < n)
            h++;
        par.assign(h, vector<int>(n, -1));
    }

    void add_edge(int x, int y, int z)
    {
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    void dfs(int x, int p, int d, ll di)
    {
        par[0][x] = p;
        depth[x] = d;
        dis[x] = di;
        for (auto to : v[x])
            if (to.first != p)
                dfs(to.first, x, d + 1, di + to.second);
    }

    void build()
    {
        dfs(0, -1, 0, 0);
        for (int i = 0; i < h - 1; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (par[i][j] < 0)
                    par[i + 1][j] = -1;
                else
                    par[i + 1][j] = par[i][par[i][j]];
            }
        }
    }

    int lca(int u, int v)
    {
        if (depth[u] > depth[v])
            swap(u, v);
        for (int i = 0; i < h; i++)
            if ((depth[v] - depth[u]) >> i & 1)
                v = par[i][v];
        if (u == v)
            return u;
        for (int i = h - 1; i >= 0; i--)
        {
            if (par[i][u] != par[i][v])
            {
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }

    ll dist(int u, int v)
    {
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }

    // int solve()
    // {
    //    ll n;
    //    cin >> n;
    //    LCA lca(n);
    //    for (int i = 0; i < n - 1; i++)
    //    {
    //       ll u, v, w;
    //       cin >> u >> v >> w;
    //       lca.add_edge(u, v, w);
    //    }
    //    lca.build();
    //    ll q;
    //    cin >> q;
    //    while (q--)
    //    {
    //       ll a, b, c;
    //       cin >> a >> b >> c;
    //       cout << (lca.dist(a, b) + lca.dist(b, c) + lca.dist(c, a)) / 2 << endl;
    //    }

    //    return 0;
    // }
};

vector<ll> compress(vector<ll> r)
{
    //1-indexed
    set<ll> se;
    for (int i = 0; i < r.size(); i++)
    {
        se.insert(r[i]);
    }

    map<ll, ll> m;
    ll cnt = 1;
    for (auto t : se)
    {
        m[t] = cnt;
        cnt++;
    }

    for (int i = 0; i < r.size(); i++)
    {
        r[i] = m[r[i]];
    }

    return r;
}

template <class Abel>
struct WeightedUnionFind
{
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    WeightedUnionFind(int n = 1, Abel SUM_UNITY = 0)
    {
        init(n, SUM_UNITY);
    }

    void init(int n = 1, Abel SUM_UNITY = 0)
    {
        par.resize(n);
        rank.resize(n);
        diff_weight.resize(n);
        for (int i = 0; i < n; ++i)
            par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x)
    {
        if (par[x] == x)
        {
            return x;
        }
        else
        {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(int x)
    {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x, int y)
    {
        return root(x) == root(y);
    }

    bool merge(int x, int y, Abel w)
    {
        w += weight(x);
        w -= weight(y);
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (rank[x] < rank[y])
            swap(x, y), w = -w;
        if (rank[x] == rank[y])
            ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(int x, int y)
    {
        return weight(y) - weight(x);
    }
};

struct SCC
{
    vector<vector<int>> G, R, T, C;
    vector<int> vs, used, blg;
    SCC() {}
    SCC(int n) : G(n), R(n), used(n), blg(n) {}

    void add_edge(int u, int v)
    {
        G[u].emplace_back(v);
        R[v].emplace_back(u);
    }

    void dfs(int v)
    {
        used[v] = 1;
        for (int u : G[v])
            if (!used[u])
                dfs(u);
        vs.emplace_back(v);
    }

    void rdfs(int v, int k)
    {
        used[v] = 1;
        blg[v] = k;
        C[k].emplace_back(v);
        for (int u : R[v])
            if (!used[u])
                rdfs(u, k);
    }

    int build()
    {
        int n = G.size();
        for (int v = 0; v < n; v++)
            if (!used[v])
                dfs(v);

        fill(used.begin(), used.end(), 0);
        int k = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (!used[vs[i]])
            {
                T.emplace_back();
                C.emplace_back();
                rdfs(vs[i], k++);
            }
        }

        for (int v = 0; v < n; v++)
            for (int u : G[v])
                if (blg[v] != blg[u])
                    T[blg[v]].push_back(blg[u]);

        for (int i = 0; i < k; i++)
        {
            sort(T[i].begin(), T[i].end());
            T[i].erase(unique(T[i].begin(), T[i].end()), T[i].end());
        }
        return k;
    }

    int operator[](int k) const { return blg[k]; }
};

vector<int> z_algorithm(const string &s)
{
    /*
    Z[i] は
    - 文字列 S=S[0]+S[1]+⋯+S[|S|−1]
    - 文字列 S[i]+S[i+1]+⋯+S[|S|−1]
    の最長共通接頭辞の長さ
    
    */
    //https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05#1-z-algorithm-%E3%81%A7%E6%B1%82%E3%82%81%E3%82%8B-z-%E9%85%8D%E5%88%97%E3%81%A8%E3%81%AF
    vector<int> prefix(s.size());
    for (int i = 1, j = 0; i < s.size(); i++)
    {
        if (i + prefix[i - j] < j + prefix[j])
        {
            prefix[i] = prefix[i - j];
        }
        else
        {
            int k = max(0, j + prefix[j] - i);
            while (i + k < s.size() && s[k] == s[i + k])
                ++k;
            prefix[i] = k;
            j = i;
        }
    }
    prefix[0] = (int)s.size();
    return prefix;
}

void YES()
{
    cout << "YES" << endl;
    exit(0);
}
void NO()
{
    cout << "NO" << endl;
    exit(0);
}

void Yes()
{
    cout << "Yes" << endl;
    exit(0);
}
void No()
{
    cout << "No" << endl;
    exit(0);
}

void m1()
{
    cout << -1 << endl;
    exit(0);
}

template <typename T>
void out(const T t) { cout << t << '\n'; }
template <typename T>
void fout(const T t) { cout << fixed << setprecision(10) << t << '\n'; }

// struct CumulativeSum2D
// {
//     int H;
//     int W;
//     vector<vector<ll>> data;

//     CumulativeSum2D(int H, int W) : H(H), W(W), data(H + 1, vector<ll>(W + 1, 0LL)) {}

//     void add(int y, int x, ll z)
//     {
//         data[y + 1][x + 1] += z;
//     }

//     void build()
//     {
//         for (int i = 1; i < data.size(); i++)
//         {
//             for (int j = 1; j < data[i].size(); j++)
//             {
//                 data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
//             }
//         }
//     }

//     void print()
//     {

//         for (int i = 0; i <= H; i++)
//         {
//             for (int j = 0; j <= W; j++)
//             {
//                 cout << data[i][j] << " ";
//             }
//             cout << endl;
//         }
//     }

//     ll query(int sx, int sy, int gx, int gy)
//     {
//         cout << sx << sy << gx << gy << endl;
        
//         fflush(stdout);

//         return (data[gy][gx] - data[sy - 1][gx] - data[gy][sx - 1] + data[sy - 1][sx - 1]);
//     }
// };

/*------------------------------*/

bool dp[110][10101];
void solve()
{
    ll n;
    cin >> n;
    ll a[n],sum=0;
    for(int i=0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum%2==1){
        out("impossible");
        exit(0);
    }
    dp[0][0] = true;
    for(int i=0; i < n; i++){
        for(int j=0; j <= 10001; j++){
            if(j-a[i]>=0){
                dp[i + 1][j] |= dp[i][j - a[i]];
            }
            dp[i + 1][j] |= dp[i][j];
        }
    }

    if(dp[n][sum/2]){
        out("possible");
    }else{
        out("impossible");
    }



}
    // g++.exe  bbb.cpp -std=c++14
    int main()
{
        cout.precision(10);
        ios::sync_with_stdio(false);
        cin.tie(0);

        solve();
        return 0;
}

//IMOSs//https://imoz.jp/algorithms/imos_method.html

/*名前
accumulate(ALL(b),0LL)
prev_permutation(ALL(v)) 辞書順で一個前の順列を構築する
bitcount    __builtin_popcountll
二次元累積和 CumulativeSum2D https://qiita.com/drken/items/56a6b68edef8fc605821#4-%E4%BA%8C%E6%AC%A1%E5%85%83%E7%B4%AF%E7%A9%8D%E5%92%8C
10進数の桁和 digit_sum
(b*b+c*c)**0.5 hypot


// 文字列t　->整数　atoi(t.c_str());
// 文字列t　->long long整数　stoll(t); ローカルではつかえない
*/

/*
**********
区間
**********
L=(1,0,1,1,3,4) C(1,3,0,1,1)
配列Lの中で x 以上 y 未満の値が何個あるのかが、累積和を使うとわかる。
具体的には C の累積和を S とすると、S[ y ] - S[ x ] で求められる

*/

/*実装例

zaatu
    sort(ALL(c));
    c.erase(unique(ALL(c)), end(c));
*******
再帰
*******
https://atcoder.jp/contests/abc015/tasks/abc015_3

**********
DP
**********
・ナップサックDP

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_C
個数制限なしナップサック　N<=100,W<=10000,v<=1000

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_B
01ナップサック　N<=100,W<=10000,v<=1000
https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_F
01ナップサック　N<=100,W<=10^9,v<=100

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H
巨大ナップザック N=40 w<10^15 , v<10^15
解）半分全列挙して、wi > wj かつvi < vj となるようなiを除いて、二分探索

・部分文字列DP 
https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd
next[i][c] := S の i 文字目以降で最初に文字 c が登場する index

https://www.hackerrank.com/contests/bbc003/challenges/bbc003-e/submissions/code/1321355726
（部分文字列の中で＋の個数の偶奇によって、カウントするか決める）

No.852 連続部分文字列
https://yukicoder.me/problems/no/852/editorial
連続な部分文字列における、文字の種類数の平均を求める
解）右端を固定すると dp[i+1] = dp[i] + (左にs[i]がでてきた位置との距離）

E - Common Subsequence
https://atcoder.jp/contests/abc130/tasks/abc130_e
文字列S、Tの共通整数列の数を求める
遷移はLCSのようにできるが、重複が発生するので除く必要がある

・桁DP
１
https://atcoder.jp/contests/abc029/tasks/abc029_d
n以下の数字の中で現れた１の数を求める
dp[i][j][k]:i桁目まで見たときに１の個数がk個の数字の個数

S - Digit Sum
https://atcoder.jp/contests/dp/tasks/dp_s
n以下の数字の中で、各桁の総和がDの倍数となるものを数える

E - Almost Everywhere Zero
https://atcoder.jp/contests/abc154/tasks/abc154_e
n以下の数字の中で,0でない数字が丁度K個あるものの数を数える

E - Sum Equals Xor
https://atcoder.jp/contests/abc129/tasks/abc129_e
a+b<=L,a+b=a^bとなる(a,b)を数える

*************
組み合わせ
*************
https://codeforces.com/contest/888/problem/D
少なくともn-k個がpi=iとなるような順列の組の数え上げ
→pi≠iとなる順列をモンモール数という。n-k~n個をpi=iと固定したときに、他の要素がpi≠iとなるような組み合わせの数（モンモール数）の積をとる

https://codeforces.com/problemset/problem/322/B
赤・青・緑の花束が存在し、ある色を３本or全ての色を１本ずつ使ったときに、できる花束の最大数

https://atcoder.jp/contests/abc021/tasks/abc021_d
https://codeforces.com/problemset/problem/1288/C
https://atcoder.jp/contests/arc023/tasks/arc023_3 aiがでかい場合→二項テーブルを使わずにbionimでやる
1 <=a1 <= a2 <= ... <= ak <= n となる（a1,a2..ak)の組の数
→等号がなければ単純にn個の要素の中からk個を選べばよい　－＞　C(n,k)
→等号がある場合は重複を許してk個選べばよい　　　　　　－＞　H(n,k)

http://codeforces.com/contest/1312/problem/D
aj < aj+i < ... ai > ....ak > ak+1 かつ同じ数字のペアが一つだけ含まれるような組の数

D - Blue and Red Balls
https://atcoder.jp/contests/abc132/tasks/abc132_d
青と赤のボールを並べ、連続している青を1~k個作ったときの並べ方の数


*************
最短経路
*************
https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e
移動できるノード数に制限がある場合の最短経路問題
→事前に幅優先探索でノード毎に移動できるノードを求めて、ダイクストラ

*************
遅延セグ木
*************
https://atcoder.jp/contests/abc153/submissions/10165699

***********
BIT
***********
https://atcoder.jp/contests/abc157/tasks/abc157_e(アルファベット毎にBITもつやつ)
https://hoj.hamako-ths.ed.jp/onlinejudge/problems/1276（中央値求めるやつ）

***********
数学
***********
大きい数の約数
https://yukicoder.me/problems/no/677
10^nの全ての正の約数を列挙
→10^kは素因数として2^k,5^kしかもたないので、それぞれをかけ合わせる
例えば10は2^1*5*1なので、2^0,2^1に5^0,5^1をそれぞれかけ合わせればよい。

************
木の直径
************
C - ロミオとジュリエット
https://atcoder.jp/contests/arc022/tasks/arc022_3
*/