結果
| 問題 | No.691 E869120 and Constructing Array 5 |
| ユーザー |
 e869120
|
| 提出日時 | 2018-05-07 20:42:25 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,555 bytes |
| コンパイル時間 | 1,216 ms |
| コンパイル使用メモリ | 98,072 KB |
| 実行使用メモリ | 27,284 KB |
| 最終ジャッジ日時 | 2024-06-28 13:33:26 |
| 合計ジャッジ時間 | 5,832 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | -- | - |
ソースコード
#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;
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;
}
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.01L;
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, vector<int>>>D1, D2;
while (D1.size() <= 35000) {
vector<int>XX; long double sum = 0;
for (int i = 0; i < 4; i++) {
int V = rand() % C[i].size();
XX.push_back(C[i][V].first); sum += C[i][V].second;
}
if (abs(sum - E / 2) < EPS) D1.push_back(make_pair(sum, XX));
}
while (D2.size() <= 35000) {
vector<int>XX; long double sum = 0;
for (int i = 0; i < 4; i++) {
int V = rand() % C[i + 4].size();
XX.push_back(C[i + 4][V].first); sum += C[i + 4][V].second;
}
if (abs(sum - E / 2) < EPS) 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;
for (int i = 0; i < D1.size(); i++) {
int pos1 = lower_bound(D2.begin(), D2.end(), make_pair(E - D1[i].first, vector<int>{})) - 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 = D1[i].second;
for (int k = 0; k < D2[pos1 - 1].second.size(); k++) GG.push_back(D2[pos1 - 1].second[k]);
}
}
if (pos1 < D1.size()) {
long double score = D1[i].first + D2[pos1].first;
if (rem > abs(E - score)) {
rem = abs(E - score); GG = D1[i].second;
for (int k = 0; k < D2[pos1].second.size(); k++) GG.push_back(D2[pos1].second[k]);
}
}
}
cout << GG.size();
for (int i = 0; i < GG.size(); i++) cout << " " << GG[i]; cout << endl;
}
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;
}