結果
| 問題 | No.5020 Averaging |
| ユーザー |
 よーちゃん
|
| 提出日時 | 2024-02-25 14:16:20 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#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 - foutdouble 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]);elseswap(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;}