#956213 (C++11) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	nikaj
提出日時	2024-02-28 08:15:53
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	718 ms / 1,000 ms
コード長	6,793 bytes
コンパイル時間	3,760 ms
コンパイル使用メモリ	113,660 KB
実行使用メモリ	6,548 KB
スコア	35,150,445
最終ジャッジ日時	2024-02-28 08:16:39
合計ジャッジ時間	39,297 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	690 ms 6,548 KB
testcase_01	AC	717 ms 6,548 KB
testcase_02	AC	692 ms 6,548 KB
testcase_03	AC	690 ms 6,548 KB
testcase_04	AC	690 ms 6,548 KB
testcase_05	AC	691 ms 6,548 KB
testcase_06	AC	688 ms 6,548 KB
testcase_07	AC	688 ms 6,548 KB
testcase_08	AC	692 ms 6,548 KB
testcase_09	AC	714 ms 6,548 KB
testcase_10	AC	687 ms 6,548 KB
testcase_11	AC	714 ms 6,548 KB
testcase_12	AC	689 ms 6,548 KB
testcase_13	AC	689 ms 6,548 KB
testcase_14	AC	691 ms 6,548 KB
testcase_15	AC	693 ms 6,548 KB
testcase_16	AC	712 ms 6,548 KB
testcase_17	AC	690 ms 6,548 KB
testcase_18	AC	689 ms 6,548 KB
testcase_19	AC	716 ms 6,548 KB
testcase_20	AC	692 ms 6,548 KB
testcase_21	AC	690 ms 6,548 KB
testcase_22	AC	695 ms 6,548 KB
testcase_23	AC	713 ms 6,548 KB
testcase_24	AC	691 ms 6,548 KB
testcase_25	AC	714 ms 6,548 KB
testcase_26	AC	690 ms 6,548 KB
testcase_27	AC	696 ms 6,548 KB
testcase_28	AC	690 ms 6,548 KB
testcase_29	AC	713 ms 6,548 KB
testcase_30	AC	689 ms 6,548 KB
testcase_31	AC	692 ms 6,548 KB
testcase_32	AC	715 ms 6,548 KB
testcase_33	AC	691 ms 6,548 KB
testcase_34	AC	688 ms 6,548 KB
testcase_35	AC	715 ms 6,548 KB
testcase_36	AC	695 ms 6,548 KB
testcase_37	AC	688 ms 6,548 KB
testcase_38	AC	694 ms 6,548 KB
testcase_39	AC	718 ms 6,548 KB
testcase_40	AC	687 ms 6,548 KB
testcase_41	AC	715 ms 6,548 KB
testcase_42	AC	715 ms 6,548 KB
testcase_43	AC	688 ms 6,548 KB
testcase_44	AC	713 ms 6,548 KB
testcase_45	AC	688 ms 6,548 KB
testcase_46	AC	688 ms 6,548 KB
testcase_47	AC	714 ms 6,548 KB
testcase_48	AC	704 ms 6,548 KB
testcase_49	AC	689 ms 6,548 KB

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

ソースコード

raw source code

int DBG = 0;
double TL = 1.0;
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <cmath>
#include <cassert>
#include <random>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
int STANDARD = 1;
using namespace std;
#define F0(i,n) for (int i=0; i<n; i++)
#define FR(i,n) for (int i=n-1; i>=0; i--)
#define F1(i,n) for (int i=1; i<=n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000000000;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const double EPS = 1e-9;
#define PR(x) cerr << #x << "=" << x << endl
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << "," << get<1>(p) << "," << get<2>(p) << ")"; return os; }
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}"; return os;
}
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}"; return os;
}

#pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize")

#ifdef XYZ
inline ll GetTSC() {
    ll lo, hi;
    asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
    return lo + (hi << 32);
}
inline double GetSeconds() {
    return GetTSC() / 3.0e9;
}
#else
#include <sys/time.h>
double GetSeconds() {
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}
#endif

const int MAX_RAND = 1 << 30;
struct Rand {
    ll x, y, z, w, o;
    Rand() {}
    Rand(ll seed) { reseed(seed); o = 0; }
    inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0;  F0(i, 20) mix(); }
    inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
    inline ll rand() { mix(); return x & (MAX_RAND - 1); }
    inline int nextInt(int n) { return rand() % n; }
    inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
    inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
    double nextDouble() { return rand() * 1.0 / MAX_RAND; }
};
Rand my(2023);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
    saveTime = GetSeconds();
    F0(i, 20) t_o[i] = 0.0;
    F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
    double tmp = Elapsed();
    cerr << "-------------------------------------" << endl;
    cerr << "Elapsed time: " << tmp << " sec" << endl;
    double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
    F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
    cerr << "-------------------------------------" << endl;
}
struct AutoTimer {
    int x;
    double t;
    AutoTimer(int x) : x(x) {
        t = Elapsed();
    }
    ~AutoTimer() {
        t_o[x] += Elapsed() - t;
    }
};
#define AT(i) AutoTimer a##i(i)
//#define AT(i)

// CONSTANTS
const int N = 64;
int n, m;
ll bscore, score;
vector<pii> bsol, sol;
ll inA[N], inB[N], A[N], B[N];
pii way[N];

const int LOGN = 1 << 16;
double logs[LOGN];

template<class T> void RS(vector<T>& v) { F1(i, SZ(v)-1) { int j = my.nextInt(0, i); swap(v[i], v[j]); } }
template<class T> T sqr(T x) { return x*x; }
const ll T = 5e17;
ll total_bscore;

void Prepare() {
    //PR(n);
    bscore = inf;
    F0(i, LOGN) logs[i] = -log((i+0.5)/LOGN);

    // solve 1D version first
    ll bv = abs(inA[0] - T);
    bsol.clear();

    my.reseed(2024);
    F0(runs, 100000) {
        F0(i, n) {
            A[i] = inA[i];
            B[i] = inB[i];
        }
        F0(it, 50) {
            F1(j, n - 1) {
                ll na = (A[0] + A[j]) / 2;
                ll nb = (B[0] + B[j]) / 2;
                ll av = max(abs(na - T), abs(nb - T));
                if (av < bv) {
                    bsol.clear();
                    F0(i, it) bsol.push_back(way[i]);
                    bsol.push_back({0, j});
                    bv = av;
                }
            }
            int i0 = 0;
            int i1 = my.nextInt(1, n-1);
            if (my.nextInt(64) == 0) i0 = my.nextInt(1, n-1);
            while (A[i0] == A[i1]) { i1 = my.nextInt(1, n-1); }
            A[i0] = A[i1] = (A[i0] + A[i1]) / 2;
            B[i0] = B[i1] = (B[i0] + B[i1]) / 2;
            way[it] = {i0, i1};
        }
    }
    // A=B 56397873
    //     34857358
    bscore = 2000000-100000*(log10(bv))+1;
    bscore = (bv == 0LL ? 2000050LL - SZ(bsol) : (long long)(2000000.0L - 100000.0L * log10(bv + 1.0L)));
    PR(bscore);
    total_bscore += bscore;
}

void UpdateBest() {
    if (score < bscore) {
        bscore = score;
        bsol = sol;
    }
}


void Solve() {
    Prepare();


    cout << SZ(bsol) << endl;
    F0(i, SZ(bsol)) {
        cout << bsol[i].first + 1 << " " << bsol[i].second + 1 << endl;
    }

    //Report();
}


void ReadInput() {
    cin >> n;
    F0(i, n) cin >> inA[i] >> inB[i];
}

int main(int argc, char* argv[]) {
    Init();

    int FIRST_TEST = 1; // atcoder
    int seed1 = FIRST_TEST, seed2 = 50;
    if(argc>1) {
        if (argc == 2) {
            seed1 = seed2 = atoi(argv[1]);
        } else {
            seed1 = atoi(argv[1]);
            seed2 = atoi(argv[2]);
        }
        STANDARD=0;
    }

    if(STANDARD) {
        ReadInput();
        Solve();
        return 0;
    }

    for (int seed=seed1; seed<=seed2; seed++) {
        if(seed>=FIRST_TEST && seed<100) {
            char inp[128];
            sprintf(inp, "in/in%03d.txt", seed);
            char outp[128];
            sprintf(outp, "out/%04d.txt", seed);
            ignore = freopen(inp, "r", stdin);
            ignore = freopen(outp, "w", stdout);
            ReadInput();
            cerr << endl << "Seed #" << seed << " " << endl;
            Solve();
            //cerr << bscore << endl;
            //cout << "Score would be " << bscore << endl;
        } else {
            // Generate
            throw;
            Rand my(seed);
        }
    }
    PR(total_bscore);

    return 0;
}

yukicoder

結果

テストケース

ソースコード