結果

問題 No.4 おもりと天秤
コンテスト
ユーザー satori16
提出日時 2016-10-11 20:46:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,250 bytes
コンパイル時間 793 ms
コンパイル使用メモリ 77,436 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-22 01:42:29
合計ジャッジ時間 5,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <functional>
#include <chrono>

//提出してからデバッグしました。
//おかしなスペシャルコードが入ってます。
//要素100個は無理・・・。Orz

#define GSI 1

typedef std::vector<std::uint64_t> 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<std::chrono::seconds>(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<std::uint64_t>());
	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;
}
0