#955409 (C++23) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	kaliafluorido
提出日時	2024-02-25 15:03:30
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	920 ms / 1,000 ms
コード長	4,434 bytes
コンパイル時間	8,837 ms
コンパイル使用メモリ	351,708 KB
実行使用メモリ	29,456 KB
スコア	21,778,092
最終ジャッジ日時	2024-02-25 15:04:32
合計ジャッジ時間	49,277 ms
ジャッジサーバーID （参考情報）	judge10 / judge14
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	763 ms 29,428 KB
testcase_01	AC	728 ms 29,428 KB
testcase_02	AC	775 ms 29,456 KB
testcase_03	AC	772 ms 29,428 KB
testcase_04	AC	742 ms 29,436 KB
testcase_05	AC	756 ms 29,432 KB
testcase_06	AC	737 ms 29,432 KB
testcase_07	AC	917 ms 29,344 KB
testcase_08	AC	783 ms 29,428 KB
testcase_09	AC	734 ms 29,428 KB
testcase_10	AC	740 ms 29,436 KB
testcase_11	AC	779 ms 29,428 KB
testcase_12	AC	790 ms 29,432 KB
testcase_13	AC	788 ms 29,428 KB
testcase_14	AC	763 ms 29,436 KB
testcase_15	AC	762 ms 29,428 KB
testcase_16	AC	775 ms 29,432 KB
testcase_17	AC	755 ms 29,436 KB
testcase_18	AC	745 ms 29,432 KB
testcase_19	AC	776 ms 29,432 KB
testcase_20	AC	750 ms 29,436 KB
testcase_21	AC	771 ms 29,424 KB
testcase_22	AC	790 ms 29,432 KB
testcase_23	AC	740 ms 29,440 KB
testcase_24	AC	791 ms 29,432 KB
testcase_25	AC	779 ms 29,432 KB
testcase_26	AC	736 ms 29,432 KB
testcase_27	AC	782 ms 29,428 KB
testcase_28	AC	734 ms 29,436 KB
testcase_29	AC	758 ms 29,432 KB
testcase_30	AC	757 ms 29,432 KB
testcase_31	AC	737 ms 29,432 KB
testcase_32	AC	784 ms 29,436 KB
testcase_33	AC	790 ms 29,432 KB
testcase_34	AC	734 ms 29,424 KB
testcase_35	AC	748 ms 29,432 KB
testcase_36	AC	716 ms 29,432 KB
testcase_37	AC	753 ms 29,432 KB
testcase_38	AC	758 ms 29,440 KB
testcase_39	AC	745 ms 29,432 KB
testcase_40	AC	768 ms 29,348 KB
testcase_41	AC	744 ms 29,432 KB
testcase_42	AC	920 ms 29,348 KB
testcase_43	AC	757 ms 29,432 KB
testcase_44	AC	736 ms 29,432 KB
testcase_45	AC	749 ms 29,424 KB
testcase_46	AC	777 ms 29,340 KB
testcase_47	AC	752 ms 29,436 KB
testcase_48	AC	753 ms 29,432 KB
testcase_49	AC	753 ms 29,432 KB

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

ソースコード

raw source code

#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));
	bool flg = true;
	while(flg){
		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()) flg = false;
			if(!flg) 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);

	auto start = chrono::system_clock::now();


	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, 10, min(5, M-t), 10);
		state.action(i,j);
		tmp_ans.push_back({i,j});
		if(state.score < best_score){
			best_score = state.score;
			ans = tmp_ans;
		}
		auto lapse = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now()-start).count();
		cerr << "t: " << t << " score: " << state.score << " lapse: " << lapse << "ms" << endl;
	}

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

	auto end = chrono::system_clock::now();
	cerr << "tot: " << chrono::duration_cast<chrono::milliseconds>(end-start).count() << "ms" << endl;

	return 0;
}

yukicoder

結果

テストケース

ソースコード