結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
コンテスト
ユーザー Aeren
提出日時 2024-02-23 22:40:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,643 bytes
コンパイル時間 3,593 ms
コンパイル使用メモリ 274,356 KB
実行使用メモリ 10,004 KB
最終ジャッジ日時 2024-09-29 07:46:01
合計ジャッジ時間 28,039 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 34
権限があれば一括ダウンロードができます

ソースコード

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 = 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;
			}
		}
		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