結果

問題 No.5016 Worst Mayor
ユーザー yunixyunix
提出日時 2023-04-29 13:25:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 4,524 bytes
コンパイル時間 1,484 ms
コンパイル使用メモリ 117,604 KB
実行使用メモリ 24,360 KB
スコア 1,050,000,000
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 13:25:15
合計ジャッジ時間 9,547 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 89 ms
23,832 KB
testcase_01 AC 84 ms
24,312 KB
testcase_02 AC 84 ms
23,328 KB
testcase_03 AC 85 ms
23,568 KB
testcase_04 AC 83 ms
23,688 KB
testcase_05 AC 84 ms
23,364 KB
testcase_06 AC 85 ms
23,568 KB
testcase_07 AC 84 ms
23,988 KB
testcase_08 AC 85 ms
24,336 KB
testcase_09 AC 84 ms
23,484 KB
testcase_10 AC 85 ms
24,000 KB
testcase_11 AC 84 ms
23,364 KB
testcase_12 AC 84 ms
23,580 KB
testcase_13 AC 86 ms
23,436 KB
testcase_14 AC 86 ms
24,360 KB
testcase_15 AC 85 ms
23,580 KB
testcase_16 AC 85 ms
23,484 KB
testcase_17 AC 86 ms
23,772 KB
testcase_18 AC 86 ms
23,340 KB
testcase_19 AC 84 ms
23,328 KB
testcase_20 AC 87 ms
23,472 KB
testcase_21 AC 84 ms
23,604 KB
testcase_22 AC 87 ms
23,592 KB
testcase_23 AC 86 ms
23,424 KB
testcase_24 AC 86 ms
23,568 KB
testcase_25 AC 84 ms
23,592 KB
testcase_26 AC 85 ms
23,976 KB
testcase_27 AC 85 ms
24,300 KB
testcase_28 AC 85 ms
23,496 KB
testcase_29 AC 85 ms
24,000 KB
testcase_30 AC 86 ms
24,000 KB
testcase_31 AC 85 ms
23,316 KB
testcase_32 AC 84 ms
24,276 KB
testcase_33 AC 86 ms
23,484 KB
testcase_34 AC 86 ms
23,988 KB
testcase_35 AC 85 ms
24,072 KB
testcase_36 AC 85 ms
23,568 KB
testcase_37 AC 85 ms
23,556 KB
testcase_38 AC 83 ms
23,676 KB
testcase_39 AC 85 ms
23,976 KB
testcase_40 AC 87 ms
23,616 KB
testcase_41 AC 85 ms
23,436 KB
testcase_42 AC 87 ms
23,688 KB
testcase_43 AC 87 ms
23,580 KB
testcase_44 AC 86 ms
24,276 KB
testcase_45 AC 84 ms
23,424 KB
testcase_46 AC 82 ms
24,060 KB
testcase_47 AC 87 ms
23,460 KB
testcase_48 AC 85 ms
23,400 KB
testcase_49 AC 84 ms
23,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
#include <bitset>
#include <time.h>

using namespace std;
using Ps = pair<short, short>;
using vec_int = vector<int>;
using P = pair<int, int>;
using P2 = pair<P, P>;
using P3 = pair<float, int>;
// using T = tuple<int, int, int>;
using T2 = tuple<float, int, int>;
using T3 = tuple<float, int, int, int, int>;
using T4 = tuple<int, int, int, int>;
using T5 = tuple<int, int, int, int, int>;
using TT = tuple<int, int, int>;
using ll = long long;
using uc = unsigned char;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int N, T;
vec_int A, B, C, D;

// #pragma GCC optimize("Ofast")


std::mt19937 mt{12345};
int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
float TIME_LIMIT = 2000;
float INV_TIME_LIMIT = 1. / 1000.;
const int JOB_MAX_LEN = 1003;
std::uniform_int_distribution<int> dist(1, RAND_RANGE);

int WAITING_TASK = 1001;

void remove_val_and_pop_from_last(vec_int &A, int val)
{
    for (int i = 0; i < A.size(); i++)
    {
        if (A.at(i) == val)
        {
            A.at(i) = A.at(A.size() - 1);
            A.pop_back();
            return;
        }
    }
    throw runtime_error("trying to remove non-existing value");
}

class Rand
{
private:
    int count = 0;
    vec_int rand_arr;

public:
    Rand(){
        rep(i, RAND_ARR_LEN){
            rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;

int Rand::get()
{
    int num = rand_arr.at(count);
    count += 1;
    count %= RAND_ARR_LEN;
    return num;
}

int Rand::get_rand(int from, int to)
{
    int diff = to - from;
    int num = get() % diff;
    return num + from;
}

float Rand::get_float()
{
    // 0~1の間の一様乱数
    return (float)get() / (float)RAND_RANGE;
}

Rand ro;

class PseudoSet
{
private:
    vec_int index_arr;

public:
    vec_int data;
    PseudoSet(){};
    PseudoSet(int value_range)
    {
        index_arr = vec_int(value_range, -1);
    }

    bool count(int value);
    void insert(int value);
    void erase(int value);
    vec_int get_data() { return data; };
    int size() { return data.size(); };
    int get_random() { return data.at(ro.get_rand(0, size())); };
};

bool PseudoSet::count(int value)
{
    return index_arr[value] != -1;
}

void PseudoSet::insert(int value)
{
    if (count(value))
        return;
    index_arr[value] = data.size();
    data.push_back(value);
}

void PseudoSet::erase(int value)
{
    if (!count(value))
    {
        // throw runtime_error("no existing value:"+to_string(value));
        return;
    }
    int tail_value = data[data.size() - 1];
    if (value == tail_value)
    {
        data.pop_back();
        index_arr[value] = -1;
    }
    else
    {
        index_arr[tail_value] = index_arr[value];
        index_arr[value] = -1;
        data[index_arr[tail_value]] = tail_value;
        data.pop_back();
    }
}

float get_time(bool init)
{
    static std::chrono::system_clock::time_point start;
    if (init)
    {
        start = std::chrono::system_clock::now();
    }
    std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); // 処理に要した時間をミリ秒に変換
}

double current_tmp(double current_time, double T0, double T1)
{
    return T1 + (T0 - T1) * (TIME_LIMIT * 0.92 - current_time) / (TIME_LIMIT * 0.92);
    // double start_time = TIME_LIMIT * 0.6;
    // double x = (current_time - start_time) / (TIME_LIMIT * 0.32);
    // return pow(T1, 1 - x) + (T0, x);
}

bool is_valid_transition(int diff, double current_time, double T0, float T1)
{
    float t = current_tmp(current_time, T0, T1);
    float rand = ro.get_float();
    // diffが正だったら常にアクセぷと
    return rand < exp(((float)diff) / t);
}



int main()
{
#ifdef OPTUNA_STUDY
    cerr << "optuna study, override parameters" << endl;
#endif
    get_time(true);
    cin >> N >> T;
    A = vec_int(N);
    B = vec_int(N);
    C = vec_int(N);
    D = vec_int(N);
    rep(i, N) cin >> A.at(i) >> B.at(i) >> C.at(i) >> D.at(i);

    // Output
    for (int i = 1; i <= T; i++)
    {
        int CurrentMoney;
        int CurrentCorps;
        cin >> CurrentMoney >> CurrentCorps;
        cout << "3" << endl;
    }

    return 0;
}
0