結果

問題 No.5016 Worst Mayor
コンテスト
ユーザー yunix
提出日時 2023-04-29 18:07:42
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,845 ms / 2,000 ms
コード長 13,910 bytes
コンパイル時間 2,476 ms
コンパイル使用メモリ 158,544 KB
実行使用メモリ 24,420 KB
スコア 22,818,503,950
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 18:09:20
合計ジャッジ時間 95,137 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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 Td = tuple<double, 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);
}




class CityMap
{
private:
    int count_highway(int num);
    double cost_between(int x, int y, int z, int w);

public:
    vector<vector<double>> horizontal_cost;
    vector<vector<double>> vertical_cost;

    CityMap();
    void upgrade_road(int x, int y, int z, int w);
    int calculate_income();
};

CityMap::CityMap()
{
    horizontal_cost = vector<vector<double>>(14, vector<double>(13, 1));
    vertical_cost = vector<vector<double>>(14, vector<double>(13, 1));
}

void CityMap::upgrade_road(int x, int y, int z, int w)
{
    if (x == z)
    {
        // この時には横方向の道
        int ymin = min(y, w);
        horizontal_cost.at(x - 1).at(ymin - 1) = 0.223;
    }
    else
    {
        int xmin = min(x, z);
        vertical_cost.at(y - 1).at(xmin - 1) = 0.223;
    }
}

double CityMap::cost_between(int x, int y, int z, int w)
{
    if (x == z)
    {
        // この時には横方向の道
        int ymin = min(y, w);
        return horizontal_cost.at(x - 1).at(ymin - 1);
    }
    else
    {
        int xmin = min(x, z);
        return vertical_cost.at(y - 1).at(xmin - 1);
    }
}

vector<P> dirs = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
int CityMap::count_highway(int num)
{
    // dijkstra法で高速道路の数を調べる
    int x1 = A.at(num);
    int y1 = B.at(num);
    int x2 = C.at(num);
    int y2 = D.at(num);

    priority_queue<Td, vector<Td>, greater<Td>> pq;
    pq.emplace(0., 0, x1, y1);

    vector<vector<double>> cost_map(15, vector<double>(15, pow(10, 9)));

    while (!pq.empty())
    {
        double cost;
        int count, x, y;
        tie(cost, count, x, y) = pq.top();
        pq.pop();
        // cerr << x << " " << y << " " << cost << " " << count << endl;
        if (cost_map.at(x).at(y) <= cost)
            continue;
        cost_map.at(x).at(y) = cost;

        if (x == x2 && y == y2)
        {
            return count;
        }

        for (int i = 0; i < 4; i++)
        {
            int dx, dy;
            tie(dx, dy) = dirs.at(i);
            int xx = x + dx;
            int yy = y + dy;
            if (xx <= 0 || xx >= 15 || yy <= 0 || yy >= 15)
                continue;
            double add_cost = cost_between(x, y, xx, yy);
            if (cost_map.at(xx).at(yy) < 10000)
                continue;
            int count2 = count;
            if (add_cost < 0.5)
                count2++;

            pq.emplace(cost + add_cost, count2, xx, yy);
        }
    }
    throw runtime_error("dijkstra must reach answer");
}

int CityMap::calculate_income()
{
    // dijkstra法で各人のベストなルートを探して、通る高速道路の本数を計算する
    int result = 0;
    for (int i = 0; i < N; i++)
    {
        // cerr << "i=" << i << " " << result << endl;
        result += 60 * count_highway(i);
    }
    return result;
}



vector<T4> road_plan;
void make_road_plan(int x0, int y0, bool reverse_x, bool reverse_y, bool xy_swap)
{
    road_plan = vector<T4>();
    // int y0 = 2;
    int y1 = y0 + 3;
    //  int x0 = 3;
    int x1 = x0 + 9;

    for (int x = x0; x < x1; x++)
    {
        if ((x - x0) % 4 < 2)
        {
            road_plan.push_back(make_tuple(x, y1, x + 1, y1));
        }
        else
        {
            road_plan.push_back(make_tuple(x, y0, x + 1, y0));
        }
    }

    for (int y = y0; y < y1; y++)
    {
        for (int x = x0; x < x1; x += 2)
        {
            road_plan.push_back(make_tuple(x, y, x, y + 1));
        }
    }

    for (int y = y1; y < 13; y++)
    {
        road_plan.push_back(make_tuple(x0, y, x0, y + 1));
        road_plan.push_back(make_tuple((x0 + x1) / 2 + 1, y, (x0 + x1) / 2 + 1, y + 1));
        road_plan.push_back(make_tuple(x1, y, x1, y + 1));
    }

    vector<T4> road_plan2;
    for (auto tmp : road_plan)
    {
        int x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = tmp;
        if (reverse_x)
            swap(x1, x2);
        if (reverse_y)
            swap(y1, y2);
        if (xy_swap)
        {
            swap(x1, y1);
            swap(x2, y2);
        }
        road_plan2.push_back(make_tuple(x1, y1, x2, y2));
    }
    road_plan = road_plan2;

    /*
    for (int y = 2; y < y0; y++)
    {
        road_plan.push_back(make_tuple(6, y, 6, y + 1));
        road_plan.push_back(make_tuple(10, y, 10, y + 1));
    }
    */

    /**/
    vector<pair<int, T4>> tmp_road_plan;
    for (auto tmp : road_plan)
    {
        int x, y, z, w;
        tie(x, y, z, w) = tmp;
        int score = abs(7 - x) + abs(7 - y);
        // cerr << score << " " << x << " " << y << endl;
        tmp_road_plan.push_back(make_pair(score, tmp));
    }
    road_plan.clear();
    // cerr << road_plan.size() << " " << tmp_road_plan.size() << endl;

    sort(tmp_road_plan.begin(), tmp_road_plan.end());
    for (auto tmp : tmp_road_plan)
    {
        road_plan.push_back(tmp.second);
    }
    // cerr << road_plan.size() << " " << tmp_road_plan.size() << endl;

    /*
        for (int y = 3; y < y0; y++)
        {
            road_plan.push_back(make_tuple(3, y, 3, y + 1));
            road_plan.push_back(make_tuple(8, y, 8, y + 1));
            road_plan.push_back(make_tuple(13, y, 13, y + 1));
        }
        for (int y = y1; y < 13; y++)
        {
            road_plan.push_back(make_tuple(8, y, 8, y + 1));
        }
        */

    /*
    for (int y = y2; y < y3; 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);

    vector<T4> best_road_plan;
    int best_income = 0;
    for (int x0 = 3; x0 <= 4; x0++)
    {
        for (int y0 = 2; y0 <= 4; y0++)
        {
            for (int swap = 0; swap < 4; swap++)
            {
                make_road_plan(x0, y0, swap % 2, (swap >> 2) % 2, (swap >> 1) % 2);
                CityMap tmp_city = CityMap();
                for (auto tmp : road_plan)
                {
                    int x0, y0, x1, y1;
                    tie(x0, y0, x1, y1) = tmp;
                    tmp_city.upgrade_road(x0, y0, x1, y1);
                }
                int tmp_income = tmp_city.calculate_income();
                // cerr << x0 << " " << y0 << " " << swap << " " << tmp_income << endl;
                if (tmp_income > best_income)
                {
                    best_income = tmp_income;
                    best_road_plan = road_plan;
                }
                road_plan.clear();
            }
        }
    }
    road_plan = best_road_plan;
    // make_road_plan();
    int money = 1000 * 1000;
    int a;
    int b;
    int turn = 0;
    int supporter_count = 64;
    rep(i, 15)
    {
        cin >> a >> b;
        cout << "3" << endl;
        turn++;
        money += 50000;
    }

    CityMap city_map = CityMap();
    int road_ind = 0;

    bool flag = false;
    int daily_income = 0;
    rep(i, supporter_count + 1)
    {
        cin >> a >> b;
        int cost_per_road = 1000 * 1000 * 10 / sqrt(i + 1); // 1.25*10^6
        // money = a;
        if (money >= cost_per_road && !flag)
        {
            int x, y, z, w;
            tie(x, y, z, w) = road_plan.at(road_ind);
            cout << "1 " << x << " " << y << " " << z << " " << w << endl;
            city_map.upgrade_road(x, y, z, w);
            road_ind++;
            money -= cost_per_road;
            flag = true;
#ifdef LOCAL
            daily_income = city_map.calculate_income();
#endif
        }
        else
        {
            cout << "2" << endl;
        }
        money += daily_income;
        turn++;
    }

    int cost_per_road = 1000 * 1000 * 10 / sqrt(supporter_count); // 1.25*10^6

    int last_income_calculation = 0;
    while (turn < 320 && road_ind < road_plan.size())
    {
        cin >> a >> b;
        // cerr << "turn:" << turn << " money:" << money << endl;

#ifdef LOCAL
#else
        if (a != money)
        {
            int diff = a - money;
            daily_income += diff;
            money = a;
        }
#endif

        if (money >= cost_per_road)
        {
            int x, y, z, w;
            tie(x, y, z, w) = road_plan.at(road_ind);
            cout << "1 " << x << " " << y << " " << z << " " << w << endl;
            city_map.upgrade_road(x, y, z, w);

#ifdef LOCAL
            if (turn > last_income_calculation)
            {
                daily_income = city_map.calculate_income();
                last_income_calculation = turn;
            }
#endif

            //}
            money -= cost_per_road;
            road_ind++;
        }
        else
        {
            money += 50000;
            cout << "3" << endl;
        }
        money += daily_income;
        turn++;
    }

    while (turn < 400)
    {
        cin >> a >> b;
        cout << "3" << endl;
        money += daily_income;
        money += 50000;
        turn++;
    }
    cerr << "score:" << money << endl;

    return 0;
}
0