結果

問題 No.5016 Worst Mayor
ユーザー yunixyunix
提出日時 2023-04-29 14:14:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 6,372 bytes
コンパイル時間 1,308 ms
コンパイル使用メモリ 115,416 KB
実行使用メモリ 24,204 KB
スコア 890,000,000
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 14:14:54
合計ジャッジ時間 8,739 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
23,832 KB
testcase_01 AC 92 ms
24,156 KB
testcase_02 AC 81 ms
23,340 KB
testcase_03 AC 87 ms
23,352 KB
testcase_04 AC 85 ms
23,364 KB
testcase_05 AC 85 ms
23,196 KB
testcase_06 AC 86 ms
23,640 KB
testcase_07 AC 87 ms
23,856 KB
testcase_08 AC 86 ms
23,364 KB
testcase_09 AC 86 ms
23,844 KB
testcase_10 AC 85 ms
23,460 KB
testcase_11 AC 86 ms
23,688 KB
testcase_12 AC 85 ms
23,460 KB
testcase_13 AC 85 ms
23,856 KB
testcase_14 AC 86 ms
23,244 KB
testcase_15 AC 85 ms
23,232 KB
testcase_16 AC 87 ms
24,156 KB
testcase_17 AC 86 ms
23,844 KB
testcase_18 AC 85 ms
23,832 KB
testcase_19 AC 91 ms
23,352 KB
testcase_20 AC 88 ms
23,856 KB
testcase_21 AC 86 ms
23,460 KB
testcase_22 AC 85 ms
23,376 KB
testcase_23 AC 86 ms
23,400 KB
testcase_24 AC 85 ms
23,832 KB
testcase_25 AC 85 ms
23,208 KB
testcase_26 AC 85 ms
24,180 KB
testcase_27 AC 86 ms
23,616 KB
testcase_28 AC 86 ms
23,820 KB
testcase_29 AC 87 ms
23,196 KB
testcase_30 AC 85 ms
23,472 KB
testcase_31 AC 86 ms
23,868 KB
testcase_32 AC 84 ms
24,072 KB
testcase_33 AC 85 ms
23,208 KB
testcase_34 AC 85 ms
24,096 KB
testcase_35 AC 84 ms
23,400 KB
testcase_36 AC 86 ms
23,472 KB
testcase_37 AC 84 ms
24,072 KB
testcase_38 AC 85 ms
23,340 KB
testcase_39 AC 86 ms
23,448 KB
testcase_40 AC 86 ms
23,256 KB
testcase_41 AC 85 ms
23,280 KB
testcase_42 AC 85 ms
23,856 KB
testcase_43 AC 85 ms
23,256 KB
testcase_44 AC 86 ms
24,144 KB
testcase_45 AC 85 ms
24,204 KB
testcase_46 AC 86 ms
23,472 KB
testcase_47 AC 84 ms
23,496 KB
testcase_48 AC 88 ms
23,220 KB
testcase_49 AC 88 ms
23,820 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);
}

vector<T4> road_plan;
void make_road_plan()
{
    road_plan = vector<T4>();
    for (int x = 3; x < 12; x++)
    {
        if ((x - 3) % 4 < 2)
        {
            road_plan.push_back(make_tuple(x, 7, x + 1, 7));
            road_plan.push_back(make_tuple(x, 9, x + 1, 9));
        }
        else
        {
            road_plan.push_back(make_tuple(x, 4, x + 1, 4));
            road_plan.push_back(make_tuple(x, 12, x + 1, 12));
        }
    }
    for (int y = 3; y < 7; y++)
    {
        road_plan.push_back(make_tuple(3, y, 3, y + 1));
        road_plan.push_back(make_tuple(5, y, 5, y + 1));
        road_plan.push_back(make_tuple(7, y, 7, y + 1));
        road_plan.push_back(make_tuple(9, y, 9, y + 1));
        road_plan.push_back(make_tuple(11, y, 11, y + 1));
        road_plan.push_back(make_tuple(13, y, 13, y + 1));
    }
    for (int y = 9; y < 12; y++)
    {
        road_plan.push_back(make_tuple(3, y, 3, y + 1));
        road_plan.push_back(make_tuple(5, y, 5, y + 1));
        road_plan.push_back(make_tuple(7, y, 7, y + 1));
        road_plan.push_back(make_tuple(9, y, 9, y + 1));
        road_plan.push_back(make_tuple(11, y, 11, y + 1));
        road_plan.push_back(make_tuple(13, y, 13, y + 1));
    }
}
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);

    int CurrentMoney;
    int CurrentCorps;
    rep(i, 64)
    {
        cin >> CurrentMoney >> CurrentCorps;
        cout << "2" << endl;
    }

    int turn = 64;
    int cost = 1000 * 1000 * 10 / 8; // road cost: 1.25*10^6

    int road_ind = 0;
    while (turn < 300 && road_ind < road_plan.size())
    {
        cin >> CurrentMoney >> CurrentCorps;

        if (CurrentMoney >= cost)
        {
            int x, y, z, w;
            tie(x, y, z, w) = road_plan.at(road_ind);
            cout << "1 " << x << " " << y << " " << z << " " << w << endl;
            road_ind++;
        }
        else
        {
            cout << "3" << endl;
        }
        turn++;
    }

    while (turn < 400)
    {
        cin >> CurrentMoney >> CurrentCorps;
        cout << "3" << endl;
        turn++;
    }

    return 0;
}
0