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

提出ソース

結果

問題	No.869 ふたつの距離
ユーザー	e869120
提出日時	2019-08-16 14:34:17
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	176 ms / 1,500 ms
コード長	3,030 bytes
コンパイル時間	1,027 ms
コンパイル使用メモリ	85,748 KB
実行使用メモリ	37,800 KB
最終ジャッジ日時	2024-09-22 06:08:12
合計ジャッジ時間	10,759 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	1 ms 6,944 KB
testcase_40	AC	2 ms 6,944 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	120 ms 20,616 KB
testcase_43	AC	36 ms 7,120 KB
testcase_44	AC	54 ms 9,560 KB
testcase_45	AC	81 ms 12,156 KB
testcase_46	AC	4 ms 6,940 KB
testcase_47	AC	23 ms 6,940 KB
testcase_48	AC	53 ms 8,288 KB
testcase_49	AC	58 ms 10,088 KB
testcase_50	AC	34 ms 8,540 KB
testcase_51	AC	7 ms 6,940 KB
testcase_52	AC	3 ms 6,940 KB
testcase_53	AC	16 ms 6,944 KB
testcase_54	AC	118 ms 17,428 KB
testcase_55	AC	70 ms 10,728 KB
testcase_56	AC	17 ms 6,940 KB
testcase_57	AC	49 ms 7,652 KB
testcase_58	AC	8 ms 6,940 KB
testcase_59	AC	15 ms 6,940 KB
testcase_60	AC	109 ms 18,052 KB
testcase_61	AC	41 ms 7,908 KB
testcase_62	AC	106 ms 20,200 KB
testcase_63	AC	141 ms 20,692 KB
testcase_64	AC	28 ms 6,944 KB
testcase_65	AC	84 ms 17,020 KB
testcase_66	AC	65 ms 12,140 KB
testcase_67	AC	169 ms 28,936 KB
testcase_68	AC	169 ms 21,284 KB
testcase_69	AC	168 ms 20,948 KB
testcase_70	AC	175 ms 21,172 KB
testcase_71	AC	170 ms 20,188 KB
testcase_72	AC	167 ms 28,792 KB
testcase_73	AC	169 ms 20,720 KB
testcase_74	AC	173 ms 20,540 KB
testcase_75	AC	171 ms 20,208 KB
testcase_76	AC	168 ms 20,024 KB
testcase_77	AC	175 ms 28,096 KB
testcase_78	AC	170 ms 28,244 KB
testcase_79	AC	170 ms 28,200 KB
testcase_80	AC	173 ms 28,860 KB
testcase_81	AC	174 ms 27,960 KB
testcase_82	AC	168 ms 20,656 KB
testcase_83	AC	173 ms 20,556 KB
testcase_84	AC	169 ms 20,416 KB
testcase_85	AC	168 ms 19,948 KB
testcase_86	AC	172 ms 19,852 KB
testcase_87	AC	169 ms 20,632 KB
testcase_88	AC	169 ms 21,052 KB
testcase_89	AC	171 ms 20,000 KB
testcase_90	AC	170 ms 21,400 KB
testcase_91	AC	176 ms 37,800 KB
testcase_92	AC	172 ms 29,120 KB
testcase_93	AC	2 ms 6,940 KB
testcase_94	AC	2 ms 6,944 KB

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

ソースコード

raw source code

#include <iostream>
#include <cassert>
#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;
	assert(1 <= N && N <= 1500);
	assert(N * (N - 1) <= 4 * A && 2 * A <= N * (N - 1));
	assert(A + N <= B && 2 * B <= N * (N - 1));
	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

結果

テストケース

ソースコード