Submission #4558294


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  int d = *max_element(A.begin(), A.end());
  vector<int> C(d+1,0);
  for(int i = 0; i < N; ++i)
    ++C[A[i]];
  if(C.back() < 2){
    cout << "Impossible" << endl;
    return 0;
  }
  for(int i = 0; i < (d+1)/2; ++i){
    if(C[i]){
      cout << "Impossible" << endl;
      return 0;
    }
  }
  //cerr << "d = " << d << ", C[(d+1)/2] = " << C[(d+1)/2] << endl;
  if((d%2 and C[(d+1)/2] != 2) or (C[(d+1)/2] != 1 and not (d%2))){
    cout << "Impossible" << endl;
    return 0;
  }
  for(int i = (d+1)/2+1; i < d; ++i){
    if(C[i] > C[i+1] or not C[i]){
      cout << "Impossible" << endl;
      return 0;
    }
  }
  cout << "Possible" << endl;
}

Submission Info

Submission Time
Task C - Tree Restoring
User TAB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 864 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 0 / 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