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

提出ソース

結果

問題	No.869 ふたつの距離
ユーザー	e869120
提出日時	2019-08-15 16:16:16
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	2,867 bytes
コンパイル時間	965 ms
コンパイル使用メモリ	85,200 KB
実行使用メモリ	36,780 KB
最終ジャッジ日時	2023-10-19 19:21:31
合計ジャッジ時間	33,705 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	2 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	2 ms 4,348 KB
testcase_40	AC	2 ms 4,348 KB
testcase_41	AC	2 ms 4,348 KB
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	AC	4 ms 4,348 KB
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	7 ms 4,392 KB
testcase_52	AC	3 ms 4,348 KB
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	AC	8 ms 4,348 KB
testcase_59	AC	15 ms 4,972 KB
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	AC	2 ms 4,348 KB
testcase_94	AC	2 ms 4,348 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 = A * S1 / (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

結果

テストケース

ソースコード