#368622 (C++14) No.869 ふたつの距離

提出ソース

結果

問題	No.869 ふたつの距離
ユーザー	e869120
提出日時	2019-08-15 16:24:44
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	199 ms / 1,500 ms
コード長	2,881 bytes
コンパイル時間	1,012 ms
コンパイル使用メモリ	85,748 KB
実行使用メモリ	36,200 KB
最終ジャッジ日時	2024-09-19 15:31:28
合計ジャッジ時間	10,754 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	133 ms 19,940 KB
testcase_43	AC	36 ms 6,992 KB
testcase_44	AC	56 ms 9,448 KB
testcase_45	AC	86 ms 11,740 KB
testcase_46	AC	4 ms 5,376 KB
testcase_47	AC	23 ms 5,376 KB
testcase_48	AC	55 ms 7,680 KB
testcase_49	AC	60 ms 9,556 KB
testcase_50	AC	34 ms 7,636 KB
testcase_51	AC	7 ms 5,376 KB
testcase_52	AC	3 ms 5,376 KB
testcase_53	AC	17 ms 5,376 KB
testcase_54	AC	125 ms 17,112 KB
testcase_55	AC	73 ms 10,712 KB
testcase_56	AC	17 ms 5,460 KB
testcase_57	AC	51 ms 7,388 KB
testcase_58	AC	8 ms 5,376 KB
testcase_59	AC	16 ms 5,376 KB
testcase_60	AC	117 ms 16,984 KB
testcase_61	AC	42 ms 7,516 KB
testcase_62	AC	118 ms 19,936 KB
testcase_63	AC	158 ms 19,812 KB
testcase_64	AC	28 ms 5,460 KB
testcase_65	AC	87 ms 15,576 KB
testcase_66	AC	69 ms 11,612 KB
testcase_67	AC	184 ms 27,860 KB
testcase_68	AC	185 ms 19,684 KB
testcase_69	AC	184 ms 19,808 KB
testcase_70	AC	189 ms 19,816 KB
testcase_71	AC	185 ms 19,680 KB
testcase_72	AC	192 ms 27,860 KB
testcase_73	AC	183 ms 19,940 KB
testcase_74	AC	182 ms 19,808 KB
testcase_75	AC	181 ms 19,812 KB
testcase_76	AC	178 ms 19,812 KB
testcase_77	AC	186 ms 27,788 KB
testcase_78	AC	189 ms 27,664 KB
testcase_79	AC	188 ms 27,664 KB
testcase_80	AC	188 ms 27,788 KB
testcase_81	AC	188 ms 27,788 KB
testcase_82	AC	182 ms 19,684 KB
testcase_83	AC	190 ms 19,804 KB
testcase_84	AC	184 ms 19,812 KB
testcase_85	AC	184 ms 19,812 KB
testcase_86	AC	190 ms 19,812 KB
testcase_87	AC	185 ms 19,676 KB
testcase_88	AC	184 ms 19,808 KB
testcase_89	AC	190 ms 19,808 KB
testcase_90	AC	183 ms 19,808 KB
testcase_91	AC	199 ms 36,200 KB
testcase_92	AC	189 ms 27,792 KB
testcase_93	AC	2 ms 5,376 KB
testcase_94	AC	3 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

bool check(int N, int A, int B, vector<pair<long double, long double>> E) {
	if (E.size() != N) return false;

	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < E.size(); i++) {
		for (int j = i + 1; j < E.size(); j++) {
			long double v = (E[i].first - E[j].first)*(E[i].first - E[j].first) + (E[i].second - E[j].second)*(E[i].second - E[j].second);
			if (v <= 100.0L) cnt1++;
			if (v <= 400.0L) cnt2++;
		}
	}
	if (cnt1 != A) return false;
	if (cnt2 != B) return false;
	return true;
}

vector<long double> construct(int P, int N, int ty) {
	if (P == 0) return vector<long double>{};

	vector<long double> V;
	long double ZA = N * N;
	for (int i = 0; i < P - 1; i++) {
		long double ZZ = 1.0L * i - 1.0L * (P - 2) / 2.0L; ZZ -= 0.314159265358979L;
		V.push_back(abs(ZZ) / ZA);
	}

	vector<long double>Z;
	for (int i = 0; i < P; i++) {
		long double sum = 0;
		for (int j = i + 1; j < P; j++) {
			sum += V[j - 1] * j;
			Z.push_back(1.0L * (10.0L - sum) / (j - i));
		}
	}
	sort(Z.begin(), Z.end());
	reverse(Z.begin(), Z.end());

	long double r = 0;
	if (N == 0) {
		if (ty == 1) r = 30.0L;
		if (ty == 2) r = 40.0L;
	}
	else if (N < Z.size()) {
		if (ty == 1) r = (2.0L * Z[N - 1] + 1.0L * Z[N]) / 3.0L;
		if (ty == 2) r = (1.0L * Z[N - 1] + 2.0L * Z[N]) / 3.0L;
	}
	else {
		if (ty == 1) r = 1e-4;
		if (ty == 2) r = 2e-4;
	}

	vector<long double>A; A.push_back(0);
	for (int i = 1; i < P; i++) {
		A.push_back(A[A.size() - 1] + r + V[i - 1] * i);
	}
	return A;
}

vector<pair<long double, long double>> solve(int N, int A, int B) {
	vector<long double>E1, E2;
	for (int i = N / 2; i <= N; i++) {
		int Z1 = i, Z2 = N - i;
		int S1 = Z1 * (Z1 - 1) / 2, S2 = Z2 * (Z2 - 1) / 2;
		int S = S1 + S2;
		if (S >= A) {
			int parity1 = 1LL * A * S1 / (1LL * (S1 + S2));
			int parity2 = A - parity1;
			E1 = construct(Z1, parity1, 1);
			E2 = construct(Z2, parity2, 2);
			break;
		}
	}

	vector<long double> T;
	for (int i = 0; i < E1.size(); i++) {
		for (int j = 0; j < E2.size(); j++) {
			long double V = 400.0L - (E1[i] - E2[j]) * (E1[i] - E2[j]);
			V = sqrtl(V);
			T.push_back(V);
		}
	}
	sort(T.begin(), T.end());
	reverse(T.begin(), T.end());

	int rem = B - (E1.size() * (E1.size() - 1) / 2) - (E2.size() * (E2.size() - 1) / 2);
	long double ret = 2.0;
	if (rem == 0) ret = 30.0L;
	else if (rem < T.size()) ret = (T[rem - 1] + T[rem]) / 2.0L;
	else ret = 10.1L;

	vector<pair<long double, long double>>ans;
	for (int i = 0; i < E1.size(); i++) ans.push_back(make_pair(0.0L, E1[i]));
	for (int i = 0; i < E2.size(); i++) ans.push_back(make_pair(ret, E2[i]));
	return ans;
}

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	vector<pair<long double, long double>> D = solve(N, A, B);
	for (int i = 0; i < N; i++) printf("%.12Lf %.12Lf\n", D[i].first, D[i].second);
	return 0;
}

yukicoder

結果

テストケース

ソースコード