結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー highjumphighjump
提出日時 2022-10-14 23:01:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,867 bytes
コンパイル時間 1,521 ms
実行使用メモリ 6,956 KB
スコア 0
最終ジャッジ日時 2022-10-14 23:03:35
合計ジャッジ時間 106,564 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge8
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 # 

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>  
#include <chrono>
#include <random>

using namespace std;

using ll = long long;
using P = pair<int, int>;
template <class T>using V = vector<T>;
template <class T>using VV = V<V<T>>;
template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }
template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }

#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)
#define MP make_pair
#define SZ(x) int(x.size())
#define ALL(x) x.begin(),x.end()
#define INF 10001000
#define endl "\n"

chrono::system_clock::time_point t_start;
const double TIME_LIMIT1 = 500, TIME_LIMIT = 1930;
double last_update = 0, t_diff;
double start_temp, end_temp;

mt19937 rng;
using uni_int = uniform_int_distribution<>;
using uni_real = uniform_real_distribution<>;
using u64 = uint64_t;
using u32 = uint32_t;

V<int> y_vec = { 0, 1,0, -1 };
V<int> x_vec = { -1, 0,1, 0 };

class XorInt {
public:
    uint32_t x = 2463534242;

    XorInt() {};

    XorInt(uint32_t seed) {
        x = 2463534242 + seed;
    };

    uint32_t next() {
        x ^= x << 13; x ^= x >> 17; x ^= x << 5;
        return x;
    }

    uint32_t operator()(uint32_t l, uint32_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint32_t operator()(uint32_t d) {
        return this->next() % d;
    }
};

XorInt xs;

class Xor64 {
public:
    uint64_t x = 88172645463325252ULL;

    Xor64() {};

    Xor64(uint64_t seed) {
        x = 88172645463325252ULL + seed;
    }

    uint64_t next() {
        x ^= x << 13; x ^= x >> 7; x ^= x << 17;
        return x;
    }

    uint64_t operator()(uint64_t l, uint64_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint64_t operator()(uint64_t d) {
        return this->next() % d;
    }
};

Xor64 xx;

void get_time() {
    auto t_now = chrono::system_clock::now();
    t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}

int N, K;
int MAX = 0;
V<int> t, u;

class Pendulum {
public:
    int b=0;
    int m=0;
    int e = 0;
    V<int> enemy;
    V<int> group;

    Pendulum(int b, int m, int e) :b(b), m(m), e(e) {
        if (b < m)b = m;
        int pos = 0;
        int count = 0;
        int amp = b;
        int dir = 1;

        FOR(time, 0, MAX) {
            if (time == t[count / 2]) {
                enemy.push_back(pos);
                count++;
            }
            else if (time == u[count / 2]) {
                group.push_back(pos);
                count++;
            }
            pos += dir;
            if (pos == amp * dir) {
                dir *= -1;
                amp = max(m, amp - e);
            }
        }
    };

};

V<Pendulum> pends,bestPends;

ll getScore() {
    ll st = 0;
    ll su = 0;

    REP(k, K) {
        double x = 0.0;
        REP(i, N)REP(j, i) {
            x += double(abs(pends[i].enemy[k] - pends[j].enemy[k])) / (pends[i].b + pends[j].b);
        }

        x *= 20000000.0;
        x /= (double(N) * (N - 1));
        st += round(x);
    }
    st /= K;

    REP(k, K) {
        int ma_dis = 0;
        REP(i, N)REP(j, i) {
            chmax(ma_dis, abs(pends[i].group[k] - pends[j].group[k]));
        }
        double x = ma_dis;
        x /= 20.0;
        x += 1;
        su += round(10000000 / x);
    }
    su /= K;

    return st * su;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    t_start = chrono::system_clock::now();

    get_time();

    cin >> N >> K;
    t = V<int>(N);
    u = V<int>(N);
    REP(i, N)cin >> t[i];
    REP(i, N)cin >> u[i];

    MAX = max(t.back(), u.back());
    int bestScore = 0;
    int B = 100;
    int M = 100;
    int E = 100;
    while (t_diff < TIME_LIMIT) {
        pends = V<Pendulum>();
        REP(i, N) {
            pends.push_back(Pendulum(xs(1, B+1), xs(1, M+1), xs(1, E+1)));
        }

        int score = getScore();
        if (chmax(bestScore, score)) {
            bestPends = pends;
        }
        get_time();
    }

    REP(i, N) {
        cout << bestPends[i].b << " " << bestPends[i].m << " " << bestPends[i].e << endl;
    }
    get_time();

    cerr << "time=" << int(t_diff) << " ms" << endl;
    cerr << "score=" << bestScore << endl;
    //cerr << "last=" << last_update << endl;
    //cerr << "cnt=" << cnt << endl;
    //cerr << "update=" << update_cnt << endl;
    return 0;
}
0