Submission #3836967
Source Code Expand
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#include <queue>
#include <regex>
#include <cassert>
#include <map>
#include <type_traits>
#include <array>
#include <cassert>
#include <typeinfo>
// #include "bits/stdc++.h"
using namespace std;
namespace {
#define rep(i, N, M) for(ll i=N, i##_len=(M); i<i##_len; ++i)
#define rep_skip(i, N, M, ...) for(ll i=N, i##_len=(M); i<i##_len; i+=(skip))
#define rrep(i, N, M) for(ll i=(M)-1, i##_len=(N-1); i>i##_len; --i)
#define pb push_back
typedef pair<double, double> pd;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tll;
typedef tuple<ll, ll, ll, ll> tll4;
typedef tuple<ll, ll, ll, ll, ll> tll5;
typedef tuple<ll, ll, ll, ll, ll, ll> tll6;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
template<typename T>
using pq_greater = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define perm(c) sort(all(c));for(bool c##perm=1;c##perm;c##perm=next_permutation(all(c)))
template<class T, class S>
T atbit(T n, S i) {
return (n >> i) % 2;
}
template<class T>
T getbit(T i) {
return 1LL << i;
}
constexpr ll POW(ll n, ll m) {
ll res = 1;
rep(i, 0, m) {
res *= n;
}
return res;
}
vll getDivisors(ll n) {
vll res;
ll i = 1;
for (; i*i < n; i++) {
if (n%i == 0) {
res.push_back(i);
res.push_back(n / i);
}
}
if (i*i == n)res.push_back(i);
sort(res.begin(), res.end());
return res;
}
vll getDivisors(ll n, ll m) {
if (n > m) swap(n, m);
vll res;
ll i = 1;
for (; i*i < n; i++) {
if (n%i == 0) {
if (m%i == 0) res.push_back(i);
if (m % (n / i) == 0) res.push_back(n / i);
}
}
if (i*i == n) if (m%i == 0) res.push_back(i);
sort(res.begin(), res.end());
return res;
}
ll gcd(ll a, ll b) {
if (a%b == 0) return b;
else return gcd(b, a%b);
}
template<
typename Inputs,
typename Functor,
typename T = typename Inputs::value_type>
void sort_by(Inputs& inputs, Functor f) {
std::sort(std::begin(inputs), std::end(inputs),
[&f](const T& lhs, const T& rhs) { return f(lhs) < f(rhs); });
}
template<int I>
vll proj(vpll v) {
vll res(v.size());
rep(i, 0, v.size()) {
if (!I) res[i] = v[i].first;
else res[i] = v[i].second;
}
return res;
}
template<int I, class T>
vll proj(T v) {
vll res(v.size());
rep(i, 0, v.size()) {
res[i] = get<I>(v[i]);
}
return res;
}
vector<pll >prime_factorize(ll n) {
vector<pll> res;
for (ll p = 2; p*p <= n; ++p) {
if (n%p != 0)continue;
ll num = 0;
while (n%p == 0) { ++num; n /= p; }
res.push_back({ p,num });
}
if (n != 1) res.push_back(make_pair(n, 1));
return res;
}
}
ll MOD = 1000000007;
ll INF = 1LL << 60;
ll n;
ll MAX_PRIME_LOWER_THAN_63BIT = 9223372036854775783;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <typename Monoid>
struct segment_tree
{
using underlying_type = typename Monoid::underlying_type;
segment_tree(ll a_n) : size_original(a_n)
{
vector<underlying_type> initial_value = vector<underlying_type>(a_n, Monoid::unit());
segment_tree_impl(a_n, initial_value);
}
segment_tree(ll a_n, vector<underlying_type>& initial_value) : size_original(a_n)
{
segment_tree_impl(a_n, initial_value);
}
void update(int i, underlying_type z) { // 0-based
assert(0 <= i && i < 2 * n - 1);
a[i + n - 1] = z;
for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
a[i - 1] = Monoid::append(a[2 * i - 1], a[2 * i]);
}
}
underlying_type query(ll l, ll r) { // 0-based, [l, r)
underlying_type lacc = Monoid::unit(), racc = Monoid::unit();
assert(l <= r && r <= n);
l += n; r += n;
for (; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
if (l % 2 == 1) lacc = Monoid::append(lacc, a[(l++) - 1]);
if (r % 2 == 1) racc = Monoid::append(a[(--r) - 1], racc);
}
return Monoid::append(lacc, racc);
}
ll size() { return size_original; }
private:
ll size_original;
ll n;
vector<underlying_type> a;
void segment_tree_impl(ll a_n, vector<underlying_type>& initial_value)
{
assert(a_n == initial_value.size());
n = 1; while (n < a_n) n *= 2;
a.resize(2 * n - 1, Monoid::unit());
rep(i, 0, initial_value.size()) {
a[i + (n - 1)] = initial_value[i];
}
rrep(i, 0, n - 1) a[i] = Monoid::append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
}
};
template <typename T>
struct min_indexed_t {
typedef pair<T, ll> underlying_type;
static underlying_type make_indexed(vector<T> v)
{
underlying_type w(v.size());
rep(i, 0, v.size()) {
w[i] = { v[i],i };
}
return w;
}
static underlying_type unit() { return make_pair(numeric_limits<T>::max(), -1); }
static underlying_type append(underlying_type a, underlying_type b) { return min(a, b); }
};
template <typename T>
struct min_t {
typedef T underlying_type;
static underlying_type unit() { return numeric_limits<T>::max(); }
static underlying_type append(underlying_type a, underlying_type b) { return min(a, b); }
};
struct linear_t {
typedef pd underlying_type;
static underlying_type unit() { return underlying_type{ 1.,0. }; }
static underlying_type append(underlying_type a, underlying_type b) {
return underlying_type{ a.first*b.first, b.first*a.second + b.second };
}
};
class Combination {
// this calculates combination (nCk).
// Constructor runs in O(MAX).
// get(n,k) returns nCk in O(1).
ll MAX, MOD;
vll fac;
vll finv;
vll inv;
public:
Combination(ll MAX = 210000, ll MOD = 1000000007)
:MOD(MOD), MAX(MAX), fac(vll(MAX)), finv(vll(MAX)), inv(vll(MAX)) {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
rep(i, 2, MAX) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
ll get(ll n, ll k) {
if (n < k)return 0;
if (n < 0 || k < 0)return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
};
ll choose(int n, int r) { // O(r) for small n
ll acc = 1;
rep(i,0, r)
acc = acc * (n - i) / (i + 1);
return acc;
}
int main() {
ll N, P;
cin >> N >> P;
vll A(N);
rep(i, 0, N) {
cin >> A[i];
A[i] = A[i] % 2;
}
sort(all(A));
ll n0 = distance(A.begin(), upper_bound(all(A), 0));
ll n1 = N - n0;
ll res = 0;
if (P == 0) {
ll res0=1LL << n0;
ll res1 = 0;
for (ll i = 0; 2 * i <= n1; ++i) {
res1 +=choose(n1, 2*i) ;
}
res = res0 * res1;
}
else {
ll res0 = 1LL << n0;
ll res1 = 0;
for (ll i = 0; 2 * i+1 <= n1; ++i) {
res1 += choose(n1,2*i+1) ;
}
res = res0 * res1 ;
}
cout << res;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Biscuits |
User |
pontaryagin |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
7325 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
1 ms |
256 KB |
in2.txt |
AC |
1 ms |
256 KB |
in3.txt |
AC |
1 ms |
256 KB |
in4.txt |
AC |
1 ms |
256 KB |
in5.txt |
AC |
1 ms |
256 KB |
in6.txt |
AC |
1 ms |
256 KB |
in7.txt |
AC |
1 ms |
256 KB |
in8.txt |
AC |
1 ms |
256 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |
sample4.txt |
AC |
1 ms |
256 KB |