#955273 (C++17) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	Pechi
提出日時	2024-02-25 13:57:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,473 bytes
コンパイル時間	3,394 ms
コンパイル使用メモリ	222,232 KB
実行使用メモリ	6,676 KB
スコア	14,180,569
最終ジャッジ日時	2024-02-25 13:57:40
合計ジャッジ時間	5,200 ms
ジャッジサーバーID （参考情報）	judge15 / judge10

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	WA	-
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	2 ms 6,676 KB
testcase_10	WA	-
testcase_11	AC	2 ms 6,676 KB
testcase_12	WA	-
testcase_13	AC	2 ms 6,676 KB
testcase_14	AC	2 ms 6,676 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	2 ms 6,676 KB
testcase_18	WA	-
testcase_19	AC	2 ms 6,676 KB
testcase_20	AC	2 ms 6,676 KB
testcase_21	AC	2 ms 6,676 KB
testcase_22	AC	1 ms 6,676 KB
testcase_23	AC	2 ms 6,676 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 6,676 KB
testcase_27	AC	2 ms 6,676 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	2 ms 6,676 KB
testcase_32	AC	2 ms 6,676 KB
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	2 ms 6,676 KB
testcase_36	AC	2 ms 6,676 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	2 ms 6,676 KB
testcase_41	WA	-
testcase_42	AC	2 ms 6,676 KB
testcase_43	AC	2 ms 6,676 KB
testcase_44	AC	1 ms 6,676 KB
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	AC	2 ms 6,676 KB
testcase_49	WA	-

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

ソースコード

raw source code

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<unordered_map>
#include<random>
#include <array>
#include <complex>
#include<chrono>
using namespace std;
#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;

chrono::system_clock::time_point starttime;
using namespace std::chrono;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif

inline float getTime() {
#ifdef DEBUG
	return duration_cast<milliseconds>(system_clock::now() - starttime).count() * 2.0;
#else
	return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}


int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };

ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); }
ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); }
inline long long int xor128() {
	static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	long long int t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

long long int pow_n(long long int x, long long int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return pow_n(x * x, n / 2);
	else
		return x * pow_n(x, n - 1);
}

int main(int argc, char* argv[]) {
	starttime = chrono::system_clock::now();
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	ll n;
	ll border = 5 * pow_n(10, 17);
	cin >> n;
	vector<ll> a(n), b(n);
	LP(i, 0, n)cin >> a[i] >> b[i];
	vector<pair<ll,ll>> ans;
	LP(t, 0, 50) {
		cerr << t<<":" << ll(2000000 - 100000 * log10(max(abs(border-a[0]), abs(border-b[0])) + 1)) << "\n";
		ll now_score = abs(a[0] - border) + abs(b[0] - border);
		ll next_score = LLONG_MAX, select = -1;
		LP(i, 1, n) {
			ll avga = (a[0] + a[i]) / 2, avgb = (b[0] + b[i]) / 2;
			ll score = abs(avga - border) + abs(avgb - border);
			if (score < next_score)select = i, next_score = score;
		}
		if (now_score > next_score) {
			ll avga = (a[0] + a[select]) / 2, avgb = (b[0] + b[select]) / 2;
			a[0] = a[select] = avga;
			b[0] = b[select] = avgb;
			ans.push_back({ 1,select + 1 });
		}
		else if (t != 49) {
			next_score = LLONG_MAX;
			ll si = -1, sk = -1;
			LP(i, 1, n) {
				LP(k, 1, i) {
					ll avgap = (a[i] + a[k]) / 2, avgbp = (b[i] + b[k]) / 2;
					ll avga = (a[0] + avgap) / 2, avgb = (b[0] + avgbp) / 2;
					ll score = abs(avga - border) + abs(avgb - border);
					if (score < next_score)si = i, sk = k, next_score = score;
				}
			}
			if (now_score < next_score)break;
			ll avgap = (a[si] + a[sk]) / 2, avgbp = (b[si] + b[sk]) / 2;
			ll avga = (a[0] + avgap) / 2, avgb = (b[0] + avgbp) / 2;
			a[si] = a[sk] = avgap;
			b[si] = b[sk] = avgbp;
			a[0] = a[si] = avga;
			b[0] = b[si] = avgb;
			ans.push_back({ si + 1,sk + 1 });
			ans.push_back({ 1,si + 1 });
		}
	}
	cerr << "score:" << ll(2000000 - 100000 * log10(max(abs(border - a[0]), abs(border - b[0])) + 1)) << "\n";
	cerr << a[0] << " " << b[0] << "\n";
	cout << ans.size() << "\n";
	ALL(x, ans)cout << x.first << " " << x.second << "\n";
	exit(0);
}

yukicoder

結果

テストケース

ソースコード