結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
ユーザー AerenAeren
提出日時 2024-02-23 22:47:59
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,515 bytes
コンパイル時間 4,042 ms
コンパイル使用メモリ 289,764 KB
実行使用メモリ 10,004 KB
最終ジャッジ日時 2024-09-29 07:56:58
合計ジャッジ時間 33,552 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 188 ms
6,816 KB
testcase_02 AC 169 ms
6,816 KB
testcase_03 AC 171 ms
6,820 KB
testcase_04 AC 236 ms
6,816 KB
testcase_05 AC 206 ms
6,824 KB
testcase_06 AC 211 ms
6,816 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 152 ms
10,004 KB
testcase_41 AC 158 ms
9,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif



int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	auto __solve_tc = [&](auto __tc_num)->int{
		int n, len;
		cin >> n >> len;
		vector<array<int, 2>> a(n);
		for(auto &[x, y]: a){
			cin >> x >> y;
		}
		auto dist = [&](int i, int j)->int{
			return abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]);
		};
		long long opt = numeric_limits<long long>::max();
		vector<int> opt_order;
		{
			vector<int> order(n);
			iota(order.begin(), order.end(), 0);
			ranges::sort(order, [&](int i, int j){ return a[i][0] != a[j][0] ? a[i][0] < a[j][0] : a[i][1] < a[j][1]; });
			vector<int> root;
			vector<int> next(n, -1);
			vector<int> active;
			for(auto i: order){
				int p = *ranges::partition_point(ranges::iota_view(0, (int)active.size()), [&](int p){ return a[active[p]][1] < a[i][1]; });
				if(p == (int)active.size()){
					root.push_back(i);
					active.push_back(i);
				}
				else{
					next[active[p]] = i;
					active[p] = i;
				}
			}
			vector<int> path;
			for(auto i = 0; i < (int)root.size(); ++ i){
				for(auto u = root[i]; ~u; u = next[u]){
					path.push_back(u);
				}
			}
			long long cost = 0;
			for(auto i = 0; i < (int)path.size() - 1; ++ i){
				cost += dist(path[i], path[i + 1]);
			}
			if(opt > cost){
				opt = cost;
				opt_order = path;
			}
		}
		{
			vector<int> order(n);
			iota(order.begin(), order.end(), 0);
			ranges::sort(order, [&](int i, int j){ return a[i][0] != a[j][0] ? a[i][0] < a[j][0] : a[i][1] > a[j][1]; });
			vector<int> root;
			vector<int> next(n, -1);
			vector<int> active;
			for(auto i: order){
				int p = *ranges::partition_point(ranges::iota_view(0, (int)active.size()), [&](int p){ return a[active[p]][1] > a[i][1]; });
				if(p == (int)active.size()){
					root.push_back(i);
					active.push_back(i);
				}
				else{
					next[active[p]] = i;
					active[p] = i;
				}
			}
			vector<int> path;
			for(auto i = 0; i < (int)root.size(); ++ i){
				for(auto u = root[i]; ~u; u = next[u]){
					path.push_back(u);
				}
			}
			long long cost = dist(path[0], path[(int)path.size() - 1]);
			for(auto i = 0; i < (int)path.size() - 1; ++ i){
				cost += dist(path[i], path[i + 1]);
			}
			if(opt > cost){
				opt = cost;
				opt_order = path;
			}
		}
		{
			vector<int> order(n);
			iota(order.begin(), order.end(), 0);
			ranges::sort(order, [&](int i, int j){ return a[i][1] != a[j][1] ? a[i][1] < a[j][1] : a[i][0] < a[j][0]; });
			vector<int> root;
			vector<int> next(n, -1);
			vector<int> active;
			for(auto i: order){
				int p = *ranges::partition_point(ranges::iota_view(0, (int)active.size()), [&](int p){ return a[active[p]][0] < a[i][0]; });
				if(p == (int)active.size()){
					root.push_back(i);
					active.push_back(i);
				}
				else{
					next[active[p]] = i;
					active[p] = i;
				}
			}
			vector<int> path;
			for(auto i = 0; i < (int)root.size(); ++ i){
				for(auto u = root[i]; ~u; u = next[u]){
					path.push_back(u);
				}
			}
			long long cost = 0;
			for(auto i = 0; i < (int)path.size() - 1; ++ i){
				cost += dist(path[i], path[i + 1]);
			}
			if(opt > cost){
				opt = cost;
				opt_order = path;
			}
		}
		{
			vector<int> order(n);
			iota(order.begin(), order.end(), 0);
			ranges::sort(order, [&](int i, int j){ return a[i][1] != a[j][1] ? a[i][1] < a[j][1] : a[i][0] > a[j][0]; });
			vector<int> root;
			vector<int> next(n, -1);
			vector<int> active;
			for(auto i: order){
				int p = *ranges::partition_point(ranges::iota_view(0, (int)active.size()), [&](int p){ return a[active[p]][0] > a[i][0]; });
				if(p == (int)active.size()){
					root.push_back(i);
					active.push_back(i);
				}
				else{
					next[active[p]] = i;
					active[p] = i;
				}
			}
			vector<int> path;
			for(auto i = 0; i < (int)root.size(); ++ i){
				for(auto u = root[i]; ~u; u = next[u]){
					path.push_back(u);
				}
			}
			long long cost = dist(path[0], path[(int)path.size() - 1]);
			for(auto i = 0; i < (int)path.size() - 1; ++ i){
				cost += dist(path[i], path[i + 1]);
			}
			if(opt > cost){
				opt = cost;
				opt_order = path;
			}
		}
		cout << n << "\n";
		for(auto i: opt_order){
			cout << a[i][0] << " " << a[i][1] << "\n";
		}
		return 0;
	};
	int __tc_cnt;
	cin >> __tc_cnt;
	for(auto __tc_num = 0; __tc_num < __tc_cnt; ++ __tc_num){
		__solve_tc(__tc_num);
	}
	return 0;
}

/*

*/
0