AtCoder Grand Contest 005

Submission #1590554

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  cin >> N;
  vint a(N);
  map<int, int> mp;
  int mx = 0;
  rep(i, N) {
    cin >> a[i];
    mp[a[i]]++;
    chmax(mx, a[i]);
  }
  auto solve = [&]() {
    for(int i = mx; i > mx/2; i--) {
      if(mp[i] < 2) return false;
      mp[i] -= 2;
    }
    if(mx%2 == 0) {
      if(mp[mx/2] < 1) return false;
      mp[mx/2]--;
    }
    for(int i = 1; i < N; i++) {
      if(i < mx/2+1+mx%2 && mp[i] > 0) return false;
    }
    return true;
  };
  cout << (solve() ? "Possible" : "Impossible") << endl;

  return 0;
}

Submission

Task問題 C - Tree Restoring
User nameユーザ名 uku
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1214 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
almostline0 AC 1 ms 256 KB
almostline1 AC 1 ms 256 KB
almostline2 AC 1 ms 256 KB
almostline3 AC 1 ms 256 KB
can0 AC 1 ms 256 KB
can1 AC 1 ms 256 KB
can2 AC 1 ms 256 KB
can3 AC 1 ms 256 KB
can4 AC 1 ms 256 KB
can5 AC 1 ms 256 KB
can6 AC 1 ms 256 KB
deg0 AC 1 ms 256 KB
deg1 AC 1 ms 256 KB
deg2 AC 1 ms 256 KB
deg3 AC 1 ms 256 KB
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
example3 AC 1 ms 256 KB
example4 AC 1 ms 256 KB
example5 AC 1 ms 256 KB
handmade0 AC 1 ms 256 KB
line0 AC 1 ms 256 KB
line1 AC 1 ms 256 KB
line2 AC 1 ms 256 KB
line3 AC 1 ms 256 KB
ng10 AC 1 ms 256 KB
ng11 AC 1 ms 256 KB
ng12 AC 1 ms 256 KB
ng13 AC 1 ms 256 KB
ng20 AC 1 ms 256 KB
ng21 AC 1 ms 256 KB
ng22 AC 1 ms 256 KB
ng23 AC 1 ms 256 KB
plus0 AC 1 ms 256 KB
plus1 AC 1 ms 256 KB
plus2 AC 1 ms 256 KB
plus3 AC 1 ms 256 KB
rand0 AC 1 ms 256 KB
rand1 AC 1 ms 256 KB
rand2 AC 1 ms 256 KB
star0 AC 1 ms 256 KB
star1 AC 1 ms 256 KB
star2 AC 1 ms 256 KB
star3 AC 1 ms 256 KB