結果

問題 No.691 E869120 and Constructing Array 5
ユーザー e869120e869120
提出日時 2018-05-07 20:56:43
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,046 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 91,308 KB
実行使用メモリ 12,860 KB
最終ジャッジ日時 2023-09-10 22:38:29
合計ジャッジ時間 5,786 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;

struct State { int p[4]; };

bool operator<(const State &a1, const State &a2) {
	for (int i = 0; i < 4; i++) {
		if (a1.p[i] < a2.p[i]) return true;
		if (a1.p[i] > a2.p[i]) return false;
	}
	return false;
}
bool operator==(const State &a1, const State &a2) {
	for (int i = 0; i < 4; i++) {
		if (a1.p[i] != a2.p[i]) return false;
	}
	return true;
}

long double Rand() {
	long double P = 0, Q = 1;
	for (int i = 0; i < 35; i++) { Q /= 2; P += 1.0L*Q*(rand() % 2); }
	return P;
}

vector<int>concatenate(State a1, State a2) {
	vector<int>T;
	for (int i = 0; i < 4; i++) T.push_back(a1.p[i]);
	for (int i = 0; i < 4; i++) T.push_back(a2.p[i]);
	return T;
}

void solve(long double E) {
	vector<long double>G;
	for (int h = 0; h < 2; h++) {
		while (true) {
			long double L = E / 8, R = E / 8, S = E / 2; L *= 2.0L / 3.0L; R *= 4.0L / 3.0L;
			vector<long double>I;
			for (int i = 0; i < 3; i++) {
				long double J = Rand()*(R - L) + L;
				I.push_back(J); S -= J;
			}
			if (S >= L && S <= R) {
				I.push_back(S); for (int j = 0; j < I.size(); j++) G.push_back(I[j]);
				break;
			}
		}
	}
	long double EPS = 0.003L;
	vector<pair<int, long double>> C[8];
	for (int i = 0; i < G.size(); i++) {
		long double T1 = G[i] - EPS, T2 = G[i] + EPS;
		int VL = (int)(1.0L*T1*T1 + 0.999), VR = (int)(1.0L*T2*T2);

		for (int j = VL; j <= VR; j++) C[i].push_back(make_pair(j, sqrtl(1.0L*j)));
	}
	vector<pair<long double, State>>D1, D2;
	while (D1.size() <= 5000) {
		State XX; long double sum = 0;
		for (int i = 0; i < 4; i++) {
			int V = rand() % C[i].size();
			XX.p[i] = C[i][V].first; sum += C[i][V].second;
		}
		if (abs(sum - E / 2) < EPS / 3) {
			D1.push_back(make_pair(sum, XX));
		}
	}
	while (D2.size() <= 5000) {
		State XX; long double sum = 0;
		for (int i = 0; i < 4; i++) {
			int V = rand() % C[i + 4].size();
			XX.p[i] = C[i + 4][V].first; sum += C[i + 4][V].second;
		}
		if (abs(sum - E / 2) < EPS / 3) {
			D2.push_back(make_pair(sum, XX));
		}
	}
	sort(D1.begin(), D1.end());
	sort(D2.begin(), D2.end());
	long double rem = 1000000.0L; vector<int>GG; State A; A.p[0] = 0; A.p[1] = 0; A.p[2] = 0; A.p[3] = 0;
	for (int i = 0; i < D1.size(); i++) {
		int pos1 = lower_bound(D2.begin(), D2.end(), make_pair(E - D1[i].first, A)) - D2.begin();

		if (pos1 >= 1) {
			long double score = D1[i].first + D2[pos1 - 1].first;
			if (rem > abs(E - score)) {
				rem = abs(E - score); GG = concatenate(D1[i].second, D2[pos1 - 1].second);
			}
		}
		if (pos1 < D1.size()) {
			long double score = D1[i].first + D2[pos1].first;
			if (rem > abs(E - score)) {
				rem = abs(E - score); GG = concatenate(D1[i].second, D2[pos1].second);
			}
		}
	}
	cout << GG.size();
	for (int i = 0; i < GG.size(); i++) cout << " " << GG[i]; cout << endl;
	//printf("Delta = %.14Lf\n", rem);
}

int main() {
	srand((unsigned)time(NULL));
	int Q; cin >> Q;
	for (int i = 1; i <= Q; i++) {
		long double A; cin >> A;
		solve(A);
	}
	return 0;
}
0