結果

問題 No.691 E869120 and Constructing Array 5
コンテスト
ユーザー e869120
提出日時 2018-05-07 21:04:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,167 bytes
コンパイル時間 1,120 ms
コンパイル使用メモリ 93,928 KB
実行使用メモリ 14,688 KB
最終ジャッジ日時 2024-06-28 13:33:44
合計ジャッジ時間 5,709 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

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) {
	while (true) {
		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);
				}
			}
		}
		if (rem < 1e-10) {
			cout << GG.size();
			for (int i = 0; i < GG.size(); i++) cout << " " << GG[i]; cout << endl;
			//printf("Delta = %.14Lf\n", rem);
			break;
		}
	}
}

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