結果

問題 No.4 おもりと天秤
ユーザー satori16satori16
提出日時 2016-10-11 20:25:49
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,990 bytes
コンパイル時間 972 ms
コンパイル使用メモリ 73,260 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 01:37:41
合計ジャッジ時間 1,832 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 7 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 WA -
testcase_06 AC 1 ms
5,248 KB
testcase_07 WA -
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 WA -
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 WA -
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 1 ms
5,248 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//提出してからデバッグしました。
//おかしなスペシャルコードが入ってます。
//要素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;
}

bool MakeHoge_r(DType A, DType B) {
	std::uint64_t WA = Sum(A);
	std::uint64_t WB = Sum(B);

	if (WA == WB) return true;
	if (WA > WB) 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) == true)return true;
		A = TA;
		B = TB;
	}
	return false;
}
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(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;
	if (D.size() > 80) return false;
	return MakeHoge_r(T, D);
}

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