Submission #2246595
Source Code Expand
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<boost/multi_array.hpp>
#include<boost/variant.hpp>
#include<boost/optional.hpp>
#include<cstdlib>
#include<ctime>
namespace lib
{
template<std::uint64_t Mod>struct modnum;
template<class T>constexpr T pow(T base, std::size_t p)
{
if (p == 0)
{
return T(1);
}
else if (p == 1)
{
return base;
}
else if (p == 2)
{
return base * base;
}
else if (p % 2 == 0)
{
return pow(pow(base, p / 2), 2);
}
else
{
return pow(pow(base, p / 2), 2)*base;
}
}
template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod> const&);
template<std::uint64_t Mod>struct modnum
{
static constexpr auto mod = Mod;
std::uint64_t val;
modnum() = default;
constexpr modnum(std::uint64_t v):val(v%Mod)
{
}
constexpr modnum& operator+=(modnum const& v)
{
val += v.val;
val %= mod;
return *this;
}
constexpr modnum& operator-=(modnum const& v)
{
val += mod - v.val;
val %= mod;
return *this;
}
constexpr modnum& operator*=(modnum const& v)
{
val *= v.val;
val %= mod;
return *this;
}
constexpr modnum& operator/=(modnum const& v)
{
return operator*=(inverse(v));
}
};
template<std::uint64_t Mod>constexpr auto operator+(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs += rhs;
}
template<std::uint64_t Mod>constexpr auto operator-(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs -= rhs;
}
template<std::uint64_t Mod>constexpr auto operator*(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs *= rhs;
}
template<std::uint64_t Mod>constexpr auto operator/(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs /= rhs;
}
template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod>const& base)
{
return pow(base, Mod - 2);
}
template<class T>constexpr auto clamp(T v)
{
return std::max(v, T());
}
template<class T>void sort(T& vec)
{
std::sort(vec.begin(), vec.end());
}
template<class T, class Compare>void sort(T& vec, Compare&& compare)
{
std::sort(vec.begin(), vec.end(), std::forward<Compare>(compare));
}
template<class T>auto lower_bound(std::vector<T>const& vec, T v)
{
return std::distance(vec.begin(), std::lower_bound(vec.begin(), vec.end(), v));
}
template<class T>auto upper_bound(std::vector<T>const& vec, T v)
{
return std::distance(vec.begin(), std::upper_bound(vec.begin(), vec.end(), v));
}
template<int val>using int_tag = std::integral_constant<int, val>;
template<class Return, class Argument>struct minimam_searcher
{
Return operator()(std::function<Return(Argument)> func, Argument beg, Argument end)const
{
Return min = std::numeric_limits<Return>::max();
for (; beg != end; ++beg)
{
min = std::min(min, func(beg));
}
return min;
}
};
template<class Return, class Argument>constexpr minimam_searcher<Return, Argument> minimam{};
template<class T>T gcd(T a, T b)
{
if (a > b)
{
return gcd(b, a);
}
if (a == T())
{
return b;
}
return gcd(b%a, a);
}
static constexpr std::int64_t intlog2(std::int64_t x)
{
for (std::int64_t i = 0, j = 2; i < 64; ++i, j <<= 1)
{
if (j > x)
{
return i;
}
}
return 64;
}
struct segtree
{
std::vector<std::int64_t> tree;
std::size_t depth_;
segtree(std::size_t depth):tree(std::size_t(1) << (depth + 1)), depth_(depth)
{
}
void change(std::size_t index, std::int64_t val)
{
change(index, val, 0);
}
std::int64_t get(std::size_t left, std::size_t right)//[left, right]の範囲
{
return get(left, right + 1, 0, 1, 0);
}
void increment(std::size_t index)
{
increment(index, 0);
}
void decrement(std::size_t index)
{
decrement(index, 0);
}
private:
std::int64_t change(std::size_t index, std::int64_t val, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
if (dep == depth_)
{
std::swap(tree[shift + index / s - 1], val);
return val;
}
else
{
auto v = change(index, val, dep + 1);
tree[shift + index / s - 1] += val - v;
return v;
}
}
std::int64_t get(std::size_t a, std::size_t b, std::size_t left, std::size_t right, std::size_t dep)
{
auto lshift = left << (depth_ - dep);
auto rshift = right << (depth_ - dep);
if (a <= lshift && rshift <= b)
{
return tree[(std::size_t(1) << dep) + left - 1];
}
else if (rshift <= a || b <= lshift)
{
return 0;
}
else
{
return
get(a, b, left << 1, left + right, dep + 1) +
get(a, b, left + right, right << 1, dep + 1);
}
}
void increment(std::size_t index, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
++tree[shift + index / s - 1];
if (dep != depth_)
{
increment(index, dep + 1);
}
}
void decrement(std::size_t index, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
--tree[shift + index / s - 1];
if (dep != depth_)
{
decrement(index, dep + 1);
}
}
};
template<class T, int N>class binary_indexed_tree
{
std::array<T, N> ar;
public:
binary_indexed_tree(T val = 0)//全ての要素をvalで初期化する
:ar{}
{
for (int i = 1; i <= N; ++i)
{
ar[i - 1] = (i&-i)*val;
}
}
void add(T val, int index)//index番の要素にvalを足す
{
++index;
for (; index <= N; index += index & -index)
{
ar[index - 1] += val;
}
}
T get(int index)const//0からindex番までの要素の和を返す
{
T ret{};
for (++index; index > 0; index -= index & -index)
{
ret += ar[index - 1];
}
return ret;
}
};
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
template<class T>auto max(std::vector<T>const& vec)
{
return *std::max_element(vec.begin(), vec.end());
}
template<class T>auto min(std::vector<T>const& vec)
{
return *std::min_element(vec.begin(), vec.end());
}
struct union_find_light
{
std::vector<int> upper;
union_find_light(std::size_t size):upper(size, -1)
{
}
int group(int index)
{
if (upper[index] == -1)
{
return index;
}
else
{
auto ret = group(upper[index]);
upper[index] = ret;
return ret;
}
}
bool merge(int x, int y)
{
auto gx = group(x);
auto gy = group(y);
if (gx != gy)
{
upper[gx] = gy;
return true;
}
return false;
}
std::map<int, std::set<int>> get()
{
std::map<int, std::set<int>> ret;
for (int i = 0; i < upper.size(); ++i)
{
ret[group(i)].emplace(i);
}
return ret;
}
};
template<class T, class Selector>void orderby(std::vector<T>& vec, Selector select)
{
lib::sort(vec, [=](T const& lhs, T const& rhs) {return select(lhs) < select(rhs); });
}
template<class T, class Selector, class U, std::size_t I>auto partition_points(T const& vec, Selector select, std::array<U, I>const& val)
{
auto first = std::begin(vec);
auto last = std::end(vec);
std::array<decltype(first), I> ret;
for (std::size_t i = 0; i < I; ++i)
{
ret[i] = std::partition_point(first, last, [=](auto const& lhs) {return select(lhs) < val[i]; });
first = ret[i];
}
return ret;
}
template<class T, class... Ts>auto make_array(T const& val, Ts const&... vals)
{
return std::array<T, sizeof...(Ts)+1>{val, vals...};
}
}
namespace std
{
template<std::uint64_t Mod>decltype(auto) operator<<(ostream& ost, lib::modnum<Mod>const& v)
{
return ost << v.val;
}
}
void Main();
int main()
{
std::cin.tie(nullptr);
std::cin.sync_with_stdio(false);
Main();
}
typedef lib::modnum<1000000007> mod_t;
void Main()
{
int N;
std::cin >> N;
std::vector<int> flags(1 << 24);
flags[0] = true;
int counts[13] = {};
++counts[0];
for (int i = 0; i < N; ++i)
{
int D;
std::cin >> D;
++counts[D];
}
std::vector<int> target;
if (counts[0])
{
for (int j = 0; j < std::min(2, counts[0]); ++j)
{
target.emplace_back(0);
}
}
for (int i = 1; i < 12; ++i)
{
for (int j = 0; j < std::min(3, counts[i]); ++j)
{
target.emplace_back(i);
}
}
if (counts[12])
{
for (int j = 0; j < std::min(2, counts[12]); ++j)
{
target.emplace_back(12);
}
}
std::vector<int> nexts(1 << 24);
for (auto const& D : target)
{
for (auto& v : nexts)
{
v = 0;
}
auto a = 1 << (12 - D);
auto b = 1 << (12 + D);
if (D == 12 || D == 0)
{
for (int i = 0; i < (1 << 24); ++i)
{
if (i&a)
{
nexts[i | a] |= std::min(3 * flags[i], 3);
}
else
{
nexts[i | a] |= flags[i];
}
}
}
else
{
for (int i = 0; i < (1 << 24); ++i)
{
if (i&a)
{
nexts[i] |= std::min(3 * flags[i], 3);
}
else
{
nexts[i | a] |= flags[i];
}
if (i&b)
{
nexts[i] |= std::min(3 * flags[i], 3);
}
else
{
nexts[i | b] |= flags[i];
}
}
}
std::swap(nexts, flags);
}
int max = -1;
for (int i = 0; i < (1 << 24); ++i)
{
if (flags[i] == 1)
{
int min = 24;
int init = 0;
for (; init < 24; ++init)
{
if ((1 << init)&i)
{
break;
}
}
if (init == 24)
{
continue;
}
int prev = init;
for (int j = prev + 1; j < 24; ++j)
{
if ((1 << j)&i)
{
min = std::min(min, j - prev);
prev = j;
}
}
min = std::min(24 - prev + init, min);
max = std::max(min, max);
}
else
{
max = std::max(max, 0);
}
}
std::cout << max << std::endl;
}
Submission Info
Submission Time |
|
Task |
C - Time Gap |
User |
plasmaeffect |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
10230 Byte |
Status |
AC |
Exec Time |
1916 ms |
Memory |
131328 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
All |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
135 ms |
131328 KB |
01-02.txt |
AC |
202 ms |
131328 KB |
01-03.txt |
AC |
267 ms |
131328 KB |
01-04.txt |
AC |
311 ms |
131328 KB |
01-05.txt |
AC |
335 ms |
131328 KB |
01-06.txt |
AC |
394 ms |
131328 KB |
01-07.txt |
AC |
525 ms |
131328 KB |
01-08.txt |
AC |
595 ms |
131328 KB |
01-09.txt |
AC |
586 ms |
131328 KB |
01-10.txt |
AC |
641 ms |
131328 KB |
01-11.txt |
AC |
605 ms |
131328 KB |
01-12.txt |
AC |
814 ms |
131328 KB |
01-13.txt |
AC |
881 ms |
131328 KB |
01-14.txt |
AC |
1239 ms |
131328 KB |
01-15.txt |
AC |
1380 ms |
131328 KB |
01-16.txt |
AC |
1916 ms |
131328 KB |
01-17.txt |
AC |
151 ms |
131328 KB |
01-18.txt |
AC |
216 ms |
131328 KB |
01-19.txt |
AC |
187 ms |
131328 KB |
01-20.txt |
AC |
232 ms |
131328 KB |
01-21.txt |
AC |
253 ms |
131328 KB |
01-22.txt |
AC |
250 ms |
131328 KB |
01-23.txt |
AC |
235 ms |
131328 KB |
01-24.txt |
AC |
331 ms |
131328 KB |
01-25.txt |
AC |
300 ms |
131328 KB |
01-26.txt |
AC |
330 ms |
131328 KB |
01-27.txt |
AC |
346 ms |
131328 KB |
01-28.txt |
AC |
345 ms |
131328 KB |
01-29.txt |
AC |
413 ms |
131328 KB |
01-30.txt |
AC |
410 ms |
131328 KB |
01-31.txt |
AC |
458 ms |
131328 KB |
01-32.txt |
AC |
493 ms |
131328 KB |
01-33.txt |
AC |
524 ms |
131328 KB |
01-34.txt |
AC |
606 ms |
131328 KB |
01-35.txt |
AC |
700 ms |
131328 KB |
01-36.txt |
AC |
743 ms |
131328 KB |
01-37.txt |
AC |
751 ms |
131328 KB |
01-38.txt |
AC |
906 ms |
131328 KB |
01-39.txt |
AC |
1421 ms |
131328 KB |
01-40.txt |
AC |
1453 ms |
131328 KB |
01-41.txt |
AC |
270 ms |
131328 KB |
01-42.txt |
AC |
232 ms |
131328 KB |
01-43.txt |
AC |
285 ms |
131328 KB |
sample-01.txt |
AC |
249 ms |
131328 KB |
sample-02.txt |
AC |
221 ms |
131328 KB |
sample-03.txt |
AC |
118 ms |
131328 KB |