結果

問題 No.5020 Averaging
ユーザー nikajnikaj
提出日時 2024-02-28 07:59:33
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,627 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 107,452 KB
実行使用メモリ 6,676 KB
スコア 0
最終ジャッジ日時 2024-02-28 08:00:00
合計ジャッジ時間 22,747 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
double total_score;

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, 40000) {
        F0(i, n) {
            A[i] = inA[i];
            B[i] = inA[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};
        }
    }
    // total_score=1524
    PR(bv / 1e17);
    total_score += log2(bv);
}

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


void Solve() {
    Prepare();


    cout << SZ(bsol) << endl;
    F0(i, SZ(bsol)) {
        cout << bsol[i].first << " " << bsol[i].second << 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_score);

    return 0;
}
0