Submission #3651832


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == 0) {
        v.clear();
        return 0;
    }
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    return i;
}

bool solve(int N, vi& a) {
    sort(ALL(a)); reverse(ALL(a));
    int F = a[0], D = a.back();
    if (!(F == D*2 || F == D*2-1)) return false;

    map<int,int> st;
    for(int ai: a) st[ai]++;

    map<int,int> sqn;
    for (int i=0,j=F; i<=F; ++i,--j) {
        int Fi = max(i, j);
        assert(IN(Fi, D, F));
        sqn[Fi]++;
    }
    for (int d=D; d<=F; ++d) {
        if (st[d] < sqn[d]) return false;
        st[d] -= sqn[d];
    }
    if (st[D] != 0) return false;

    return true;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << (solve(N,a) ? "Possible":"Impossible") << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Tree Restoring
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2959 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3, example4, example5
All 700 / 700 almostline0, almostline1, almostline2, almostline3, can0, can1, can2, can3, can4, can5, can6, deg0, deg1, deg2, deg3, example0, example1, example2, example3, example4, example5, handmade0, line0, line1, line2, line3, ng10, ng11, ng12, ng13, ng20, ng21, ng22, ng23, plus0, plus1, plus2, plus3, rand0, rand1, rand2, star0, star1, star2, star3
Case Name Status Exec Time Memory
almostline0 1 ms 256 KB
almostline1 1 ms 256 KB
almostline2 1 ms 256 KB
almostline3 1 ms 256 KB
can0 1 ms 256 KB
can1 1 ms 256 KB
can2 1 ms 256 KB
can3 1 ms 256 KB
can4 1 ms 256 KB
can5 1 ms 256 KB
can6 1 ms 256 KB
deg0 1 ms 256 KB
deg1 1 ms 256 KB
deg2 1 ms 256 KB
deg3 1 ms 256 KB
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
example3 1 ms 256 KB
example4 1 ms 256 KB
example5 1 ms 256 KB
handmade0 1 ms 256 KB
line0 1 ms 256 KB
line1 1 ms 256 KB
line2 1 ms 256 KB
line3 1 ms 256 KB
ng10 1 ms 256 KB
ng11 1 ms 256 KB
ng12 1 ms 256 KB
ng13 1 ms 256 KB
ng20 1 ms 256 KB
ng21 1 ms 256 KB
ng22 1 ms 256 KB
ng23 1 ms 256 KB
plus0 1 ms 256 KB
plus1 1 ms 256 KB
plus2 1 ms 256 KB
plus3 1 ms 256 KB
rand0 1 ms 256 KB
rand1 1 ms 256 KB
rand2 1 ms 256 KB
star0 1 ms 256 KB
star1 1 ms 256 KB
star2 1 ms 256 KB
star3 1 ms 256 KB