結果

問題 No.4 おもりと天秤
ユーザー satori16satori16
提出日時 2016-10-11 20:46:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4,001 ms / 5,000 ms
コード長 2,252 bytes
コンパイル時間 710 ms
コンパイル使用メモリ 77,356 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-08 17:11:48
合計ジャッジ時間 5,764 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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+1; 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