結果

問題 No.5020 Averaging
コンテスト
ユーザー kaliafluorido
提出日時 2024-02-25 14:53:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,003 bytes
コンパイル時間 8,798 ms
コンパイル使用メモリ 351,664 KB
実行使用メモリ 218,152 KB
スコア 0
最終ジャッジ日時 2024-02-25 14:53:48
合計ジャッジ時間 13,347 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

#define ALL(a) (a).begin(), (a).end()
#define FOR(i, start, end) for (int i = start; i < (int)(end); ++i)
#define RFOR(i, rstart, rend) for (int i = rstart; i >= (int)(rend); --i)
#define REP(i, end) FOR(i, 0, end)

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr ll LINF = 1LL << 60;
constexpr int INF = 1 << 30;

template <class T> using PQ = priority_queue<T, vector<T>, greater<T>>;

template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }
template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }

class Xorshift{
    unsigned x, y, z, w;
public:
    Xorshift(unsigned seed = 123456789) : x(seed), y(362436069), z(521288629), w(88675123) {}

    unsigned xor128(){
        unsigned t;
        t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
    }
    
    // [a, b) の int 乱数を生成
    int irand(int a, int b){
        return a + (xor128() % (b - a));
    }
    
    // [0.0, 1.0) の double 乱数を生成
    double drand(){
        return xor128() / 4294967296.0; // UINT_MAX+1 = 4294967296
    }
    
    // [a, b) の double 乱数を生成
    inline double drand(double a, double b){
        return a + drand() * (b - a);
    }
};

struct Timekeeper{
	Timekeeper(const int64_t &t) : start_time(std::chrono::high_resolution_clock::now()),time_threshold(t) {}

	bool is_timeout(){
		auto end_time = std::chrono::high_resolution_clock::now();
		return std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count() >= time_threshold;
	}

private:
	std::chrono::high_resolution_clock::time_point start_time;
	int64_t time_threshold;
};

constexpr int N = 45;
constexpr int M = 50;
constexpr ll G = 5e17;
int n;
Xorshift rnd;
vector<ll> A(N),B(N);
vector<pii> ans;

struct State{
	vector<ll> a,b;
	double score=-1;
	pii first_action={-1,-1};
	State() {}
	State(const vector<ll> &_a, const vector<ll> &_b) : a(_a), b(_b) { calc_score(); }

	void calc_score(){
		ll v = max(abs(a[0]-G), abs(b[0]-G)+1);
		score = log(v);
	}

	void action(int i, int j){
		ll na = (a[i]+a[j])/2;
		ll nb = (b[i]+b[j])/2;
		a[i] = na;
		b[i] = nb;
		a[j] = na;
		b[j] = nb;
		calc_score();
	}
};

using StatePtr = shared_ptr<State>;
bool operator<(const StatePtr &a, const StatePtr &b){
	return a->score > b->score;
}

pii chokudaiSearchAction(
	const State &state,
	const int beam_width,
	const int beam_depth,
	const int64_t time_threshold
){
	auto timekeeper = Timekeeper(time_threshold);
	auto beam = vector<priority_queue<StatePtr>>(beam_depth+1);
	beam[0].push(make_shared<State>(state));
	while(true){
		REP(t,beam_depth){
			auto &now_beam = beam[t];
			auto &next_beam = beam[t+1];
			REP(i,beam_width){
				if(now_beam.empty()) break;
				State now_state = *now_beam.top();
				now_beam.pop();
				REP(i,n)FOR(j,i+1,n){
					if(now_state.a[i] == now_state.a[j] && now_state.b[i] == now_state.b[j]) continue;
					State next_state = now_state;
					next_state.action(i,j);
					if(t==0){
						next_state.first_action = {i,j};
					}
					next_beam.push(make_shared<State>(next_state));

				}
			}
		}
		if(timekeeper.is_timeout()) break;
	}
	RFOR(t,beam_depth,0){
		if(!beam[t].empty()){
			return beam[t].top()->first_action;
		}
	}
	return {-1,-1};
}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> n;
	REP(i,n) cin >> A[i] >> B[i];
	State state(A,B);
	double best_score = state.score;
	vector<pii> tmp_ans;
	REP(t,M){
		auto [i,j] = chokudaiSearchAction(state, 5, M-t, 15);
		state.action(i,j);
		tmp_ans.push_back({i,j});
		if(state.score < best_score){
			best_score = state.score;
			ans = tmp_ans;
		}
	}

	cout << ans.size() << endl;
	for (auto [a, b] : ans) cout << a+1 << " " << b+1 << endl;

	return 0;
}
0