#955315 (C++14) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	よーちゃん
提出日時	2024-02-25 14:16:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	955 ms / 1,000 ms
コード長	7,474 bytes
コンパイル時間	1,662 ms
コンパイル使用メモリ	131,500 KB
実行使用メモリ	11,492 KB
スコア	36,406,699
最終ジャッジ日時	2024-02-25 14:17:13
合計ジャッジ時間	51,793 ms
ジャッジサーバーID （参考情報）	judge10 / judge14
	純コード判定しない問題か言語

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>
#include <time.h>
#include <atcoder/dsu.hpp>

#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

bool debug = false; // false : 提出, true : fin - fout
double time_ratio = 1.0;
string file_No = "0000";
ifstream fin;
ofstream fout;
ofstream fout_debug;
ofstream fout_score;
int Gaussian_size = 1000000;
vector<double> Gaussian_(Gaussian_size);
struct timespec timeini;

const vi dx = { -1, 1, 0, 0 };
const vi dy = { 0, 0, -1, 1 };
const ll V = 500000000000000000LL;

void debug_init() {
	string txt = ".txt";

	string ifname = "in\\";
	ifname = ifname + file_No + txt;
	fin.open(ifname);
	string ofname = "out\\";
	ofname = ofname + file_No + txt;
	fout.open(ofname);
	string ofname_debug = "debug\\";
	ofname_debug = ofname_debug + file_No + txt;
	fout_debug.open(ofname_debug);
	string ofname_score = "score\\";
	ofname_score = ofname_score + file_No + txt;
	fout_score.open(ofname_score);

	time_ratio = 0.6; // 5950X
	// time_ratio = 0.7; // 12700KF
}

void debug_end() {
	fin.close();
	fout.close();
	fout_debug.close();
}

double time_diff()
{
	struct timespec timetmp;
	timespec_get(&timetmp, TIME_UTC);
	double ans = timetmp.tv_nsec - timeini.tv_nsec;
	ans += (double)(timetmp.tv_sec - timeini.tv_sec) * 1000000000.0;
	return time_ratio * ans / 1000000.0;
}

int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

double RAND_() {
	double rand_ = (double)(xor128()) / (double)INT32_MAX;
	return rand_;
}

double Gaussian() {
	double X = RAND_();
	double Y = RAND_();
	double Z = sqrt(-2.0 * log(X)) * cos(2.0 * acos(-1.0) * Y);
	return Z;
}


struct Input {
	int N;
	ll A[45], B[45];

	void readProblem(istream& in = cin) {
		in >> N;
		rep(i, N)
			in >> A[i] >> B[i];
		return;
	}
};

struct Output {
	int X = 0;
	vi u, v;
	void resize_all() {

	}
	void writeSolution(ostream& out = cout) {
		out << X << "\n";
		rep(x, X)
			out << u[x] + 1 << " " << v[x] + 1 << "\n";
		return;
	}
};

Input input;
Output output;

struct Info {
	int N;
	void resize_all(int N_) {
		N = N_;

		return;
	}
};

Info info;

bool is_inside(int x, int y) {
	int N = input.N;
	if (x < 0) return false;
	if (y < 0) return false;
	if (x >= N) return false;
	if (y >= N) return false;
	/*
	int H = input.H;
	int W = input.W;
	if (x < 0) return false;
	if (y < 0) return false;
	if (x >= H) return false;
	if (y >= W) return false;
	*/
	return true;
}

ll Atmp[45], Btmp[45];

ll scall() {
	int N = input.N;
	rep(i, N) {
		Atmp[i] = input.A[i];
		Btmp[i] = input.B[i];
	}
	rep(x, output.X) {
		int u = output.u[x];
		int v = output.v[x];
		ll Aval = (Atmp[u] + Atmp[v]) / 2LL;
		ll Bval = (Btmp[u] + Btmp[v]) / 2LL;
		Atmp[u] = Aval;
		Atmp[v] = Aval;
		Btmp[u] = Bval;
		Btmp[v] = Bval;
	}
	return -max(abs(V - Atmp[0]), abs(V - Btmp[0]));
}

int Xnew;
vi unew, vnew;
ll sctmp() {
	int N = input.N;
	rep(i, N) {
		Atmp[i] = input.A[i];
		Btmp[i] = input.B[i];
	}
	rep(x, Xnew) {
		int u = unew[x];
		int v = vnew[x];
		ll Aval = (Atmp[u] + Atmp[v]) / 2LL;
		ll Bval = (Btmp[u] + Btmp[v]) / 2LL;
		Atmp[u] = Aval;
		Atmp[v] = Aval;
		Btmp[u] = Bval;
		Btmp[v] = Bval;
	}
	return -max(abs(V - Atmp[0]), abs(V - Btmp[0]));
}

ll score(ll sc) {
	return (ll)(2000000.0 - 100000.0 * log10(-sc + 1));
}

void solve_init() {
	int N = input.N;
	output.resize_all();
	info.resize_all(N);

	return;
}

void solveA() {
	int N = input.N;

	return;
}

void solveB() {
	int N = input.N;

	ll sc = scall();




	double start_temp = 15.0;
	double end_temp = 5.0;
	double TIME_LIMIT = 950.0;
	ll loop_count = 0;
	double time_now = 0.0;
	double temp = 0.0;

	while (1) {
		//break;
		if (loop_count % 1000 == 0) {
			time_now = time_diff();
			if (time_now > TIME_LIMIT)
				break;
			temp = pow(10.0, start_temp + (end_temp - start_temp) * time_now / TIME_LIMIT);
		}

		loop_count++;
		ll scdiff = 0;

		int type = xor128() % 4;
		if (type == 0) {
			//continue;
			if (output.X == 0) continue;
			int x = xor128() % output.X;
			int utmpold = output.u[x];
			int vtmpold = output.v[x];
			int utmpnew = output.u[x];
			int vtmpnew = output.v[x];
			int t = xor128() % 3;
			if (t == 0) {
				utmpnew = xor128() % N;
				if (utmpnew == utmpold) continue;
				if (utmpnew == vtmpnew) continue;
			}
			else if (t == 1) {
				vtmpnew = xor128() % N;
				if (vtmpnew == vtmpold) continue;
				if (vtmpnew == utmpnew) continue;
			}
			else if (t == 2) {
				utmpnew = xor128() % N;
				vtmpnew = xor128() % N;
				if (utmpnew == utmpold && vtmpnew == vtmpold) continue;
				if (utmpnew == vtmpnew) continue;
			}
			Xnew = output.X;
			unew = output.u;
			vnew = output.v;
			unew[x] = utmpnew;
			vnew[x] = vtmpnew;
		}
		else if (type == 1) {
			//continue;
			if (output.X == 50) continue;
			int utmpnew = xor128() % N;
			int vtmpnew = xor128() % N;
			if (utmpnew == vtmpnew) continue;
			int x = xor128() % (output.X + 1);
			Xnew = output.X + 1;
			unew = output.u;
			vnew = output.v;
			unew.insert(unew.begin() + x, utmpnew);
			vnew.insert(vnew.begin() + x, vtmpnew);
		}
		else if (type == 2) {
			//continue;
			if (output.X == 0) continue;
			int x = xor128() % (output.X);
			Xnew = output.X - 1;
			unew = output.u;
			vnew = output.v;
			unew.erase(unew.begin() + x);
			vnew.erase(vnew.begin() + x);
		}
		else if (type == 3) {
			//continue;
			if (output.X < 2) continue;
			int x1 = xor128() % (output.X);
			int x2 = xor128() % (output.X);
			if (x1 == x2) continue;
			Xnew = output.X;
			unew = output.u;
			vnew = output.v;
			swap(unew[x1], unew[x2]);
			swap(vnew[x1], vnew[x2]);
		}
		else if (type == 4) {
			//continue;
			if (output.X < 2) continue;
			int x1 = xor128() % (output.X);
			int x2 = xor128() % (output.X);
			if (x1 == x2) continue;
			if (output.u[x1] == output.v[x2]) continue;
			if (output.u[x2] == output.v[x1]) continue;
			if (x1 == x2) continue;
			Xnew = output.X;
			unew = output.u;
			vnew = output.v;
			if (xor128() % 2 == 0)
				swap(unew[x1], unew[x2]);
			else
				swap(vnew[x1], vnew[x2]);
		}

		ll scnew = sctmp();
		scdiff = scnew - sc;

		double prob = exp((double)scdiff / temp);
		//if (scdiff > 0) {
		if (prob > RAND_()) {
			//if (scdiff > 0.0)
				//cout << "!" << sc << " " << temp << endl;
			output.X = Xnew;
			output.u = unew;
			output.v = vnew;
			sc = scnew;
		}
	}

	fout_score << score(sc) << endl;
	return;
}

int main(int argc, char* argv[]) {
	if (argc >= 2) file_No = argv[1];
	timespec_get(&timeini, TIME_UTC);
	if (debug)
		debug_init();
	debug ? input.readProblem(fin) : input.readProblem();
	solve_init();
	solveA();
	solveB();
	debug ? output.writeSolution(fout) : output.writeSolution();
	if (debug)
		debug_end();
	return 0;
}

yukicoder

結果

テストケース

ソースコード