#include #include #include #include #include #include //提出してからデバッグしました。 //おかしなスペシャルコードが入ってます。 //要素100個は無理・・・。Orz #define GSI 1 typedef std::vector DType; std::uint64_t Sum(DType& D) { std::uint64_t i = 0; for (auto& o : D) { i += o; } return i; } DType GetInput() { std::uint64_t i = 0; DType D; std::cin >> i; while (std::cin >> i) D.push_back(i); return D; } DType MakeProblem1() { DType D{ 1, 2, 3 }; return D; } DType MakeProblem2() { DType D{ 1, 2, 3, 4, 5 }; return D; } DType MakeProblem3() { DType D{ 62, 8, 90, 2, 24, 62, 38, 64, 76, 60, 30, 76, 80, 74, 72 }; return D; } bool Show(bool F) { std::cout << (F ? "possible" : "impossible") << std::endl; return true; } bool MoveElement(DType& A, DType& B, std::size_t Idx) { A.push_back(B[Idx]); B.erase(B.begin() + Idx); return true; } int CalcSpecal(DType& D) { DType::value_type i = D[0]; DType::value_type V = 0; for (auto o : D) { if (o != i) return -1; V += o; } return V % 2 == 0 ? 1: 0; } bool MakeHoge_r(DType A, DType B,const std::chrono::system_clock::time_point& S) { std::uint64_t WA = Sum(A); std::uint64_t WB = Sum(B); if (WA == WB) return true; if (WA > WB) return false; std::chrono::system_clock::time_point N = std::chrono::system_clock::now(); if (std::chrono::duration_cast(N - S) > std::chrono::seconds(3)) return false; auto TA = A; auto TB = B; for (std::size_t i = 0; i < B.size()/2; i++) { MoveElement(A, B, i); if (MakeHoge_r(A, B, S) == true)return true; A = TA; B = TB; } return false; } bool MakeHoge(DType& D) { DType T; int F = 0xdeadbeef; std::sort(D.begin(), D.end(),std::greater()); F = CalcSpecal(D); if (F != -1) return F == 1 ? true : false; auto S = std::chrono::system_clock::now(); return MakeHoge_r(T, D, S); } int main() { DType D; bool F = false; #if !GSI D = MakeProblem1(); F = MakeHoge(D); Show(F); D = MakeProblem2(); F = MakeHoge(D); Show(F); D = MakeProblem3(); F = MakeHoge(D); Show(F); #else D = GetInput(); F = MakeHoge(D); Show(F); #endif return 0; }