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
AC × 3
AC × 49
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