#864615 (C++17(gcc12)) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: 7iz6
• 提出日時: 2023-04-29 16:22:32
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,973 ms / 2,000 ms
• コード長: 11,411 bytes
• コンパイル時間: 7,749 ms
• コンパイル使用メモリ: 230,772 KB
• 実行使用メモリ: 26,976 KB
• スコア: 19,507,652,440
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2023-04-29 16:25:56
• 合計ジャッジ時間: 107,349 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC optimize("-O3")

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <array>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <bitset>
#include <random>
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <numeric>
#include <chrono>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <memory>
#include <optional>


struct Point {
  int i, j;
};

bool operator<(const Point& lhs, const Point& rhs) {
  return (lhs.i < rhs.i || lhs.j < rhs.j);
}

bool operator>(const Point& lhs, const Point& rhs) {
  return (lhs.i > rhs.i || lhs.j > rhs.j);
}

struct Road {
  Point u, v;
};

bool operator==(const Point& lhs, const Point& rhs) {
  return (lhs.i == rhs.i && lhs.j == rhs.j);
}

// --------------------- macros ----------------------
#define pii std::pair<int,int>
#define Vec std::vector
#define rep(i, s, n) for(int i = s; i < (n); i++)


using namespace std;
using ll = long long;

// --------------------- constants ----------------------
constexpr int INF = 1e9 + 10;
constexpr ll LINF = 1LL<<60;
constexpr double EPS = 1e-6;
const double PI = std::acos(-1);

// clockwise
static const int di[4] = {0, 1, 0, -1};
static const int dj[4] = {1, 0, -1, 0};

const double TL = 2.0;
const double TL_90 = TL * 0.9;
const double TL_95 = TL * 0.95;

constexpr int N = 3000;
constexpr int TERM = 400;
constexpr int H = 14;
constexpr int W = 14;
constexpr int INIT_FUND = 1'000'000;
constexpr double TIME_ROAD = 1.0;
constexpr double TIME_HIGHWAY = 0.223;
constexpr int DONATION = 50'000;
constexpr int FEE_HIGHWAY = 60;


// --------------------- global variables ----------------------
std::random_device seed_gen;
std::mt19937 mt(seed_gen());

clock_t start_time, cur_time;

Point A[N], C[N];

// --------------------- functionss ----------------------
double get_time() {
  return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}

bool is_out(int i, int j, int d) {
  return (i < 0 || i >= d || j < 0 || j >= d);
}

bool is_out(int i, int j, int h, int w) {
  return (i < 0 || i >= h || j < 0 || j >= w);
}

template<typename T> T pow2(T a) {
  return a * a;
}

bool arg_parse(int argv, char* argc[]) {
  for(int i = 0; i < argv; i++) {
    if(std::strcmp(argc[i], "--seed") == 0) {
      if(i + 1 > argv) {
        std::cerr << "no arguments." << std::endl;
        return false;
      }
      int _seed = std::stoi(argc[i+1]);
      mt = std::mt19937(_seed);
    }
  }
  return true;
}

// --------------------- classes ----------------------
struct IOServer {
  int patron = 1;
  int fund = INIT_FUND;
  void read_output1(int i1, int j1, int i2, int j2) {

    fund -= std::floor((double)10000000 / std::sqrt(patron));

  }

  void read_output2() {
    patron++;
  }

  void read_output3() {
    fund += DONATION;
  }

};
// ----------------------------------------------------


struct Result {
  int k;
  long long score;
};

class Solver {
public:
  Result best_result;
  int num_search = 0;
  int money;
  int patron;
  Road p_road; // priority road
  Vec<Vec<Vec<Vec<int>>>> cnt;
  Vec<Vec<Vec<double>>> dist_cur;
  Vec<Vec<Vec<Vec<bool>>>> is_highway;
  Vec<pair<Point,Point>> highway_list;
  Vec<int> num_highway_on_path;
  int num_reward = 0;

  int num_highway;

  #ifdef LOCAL
  IOServer judge;
  #endif
  
  Solver() {
  } // constructor

  void init() {
    int buf;
    std::cin >> buf >> buf;
    for(int i = 0; i < N; i++) {
      std::cin >> A[i].i >> A[i].j >> C[i].i >> C[i].j;
      A[i].i--;
      C[i].i--;
      A[i].j--;
      C[i].j--;
    }

    patron = 1;
    money = INIT_FUND;
    num_highway = 0;
    cnt.resize(H, Vec<Vec<Vec<int>>>(W, Vec<Vec<int>>(H, Vec<int>(W, 0))));
    is_highway.resize(H, Vec<Vec<Vec<bool>>>(W, Vec<Vec<bool>>(H, Vec<bool>(W, false))));
    dist_cur.resize(N, Vec<Vec<double>>(H, Vec<double>(W, 1e18)));
    num_highway_on_path.resize(N, 0);

    // BFS
    Vec<Vec<int>> dist;
    for(int i = 0; i < N; i++) {
      dist.clear();
      dist.resize(H, Vec<int>(W, INF));
      if(A[i] == C[i]) continue;

      queue<pair<int, Point>> q;
      dist[A[i].i][A[i].j] = 0;
      q.push(std::make_pair(0, A[i]));
      bool ok = false;
      int ni, nj;

      while(!q.empty() && !ok) {
        auto[cost, p] = q.front(); q.pop();

        for(int d = 0; d < 4; d++) {
          ni = p.i + di[d];
          nj = p.j + dj[d];
          if(is_out(ni,nj,H,W)) continue;

          if(dist[ni][nj] > cost+1) {
            dist[ni][nj] = cost + 1;
            q.push(std::make_pair(cost+1, Point{ni,nj}));
          }
          if(ni == C[i].i && nj == C[i].j) {
            ok = true;
            break;
          }
        }
      }

      // 復元
      queue<pair<int,Point>> q_rev;
      Vec<Vec<bool>> visited(H, Vec<bool>(W, false));
      q_rev.push({dist[C[i].i][C[i].j], C[i]});
      ok = false;
      visited[C[i].i][C[i].j] = true;

      while(!q_rev.empty() && !ok) {
        auto[d, p] = q_rev.front(); q_rev.pop();
        
        for(int dir = 0; dir < 4; dir++) {
          ni = p.i + di[dir];
          nj = p.j + dj[dir];
          if(is_out(ni,nj,H,W)) continue;

          if(dist[ni][nj] == d - 1) {

            cnt[ni][nj][p.i][p.j]++;
            cnt[p.i][p.j][ni][nj]++;

            if(!visited[ni][nj]) {
              visited[ni][nj] = true;
              q_rev.push(std::make_pair(d-1, Point{ni,nj}));
            }

          }
        }
      }
    }

    int max_cnt = -1;
    rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt){
      max_cnt=cnt[i][j][k][l];
      p_road = {Point{i,j}, Point{k,l}};
    }

    fprintf(stderr, "[case] N: %d, TERM: %d\n", N, TERM);

  }

  // main solve
  void solve() {
    int pre_choice = -1;

    for(int t = 0; t < TERM; t++) {
      int nil;

      #ifndef LOCAL
      std::cin >> money >> patron;
      // scanf("%d %d", &money, &patron);
      #endif

      #ifdef LOCAL
      if(t % 20 == 0) {
        fprintf(stderr, 
          "[Info] TERM: %03d, time: %6.3f, money: %9d, patron: %2d\n", t, get_time(), money, patron
        );
        fprintf(stderr, 
          "...... Number of Highway: %2d, \n", num_highway
        );
        fprintf(stderr, 
          "...... Number of Highway on path: %3d, \n\n", num_reward
        );
      }
      #endif

      // 60日までは協力者集め
      if(t < 59) {

        std::cout << "2" << std::endl;
        pre_choice = 2;
        patron++;

      } else {
        if(get_time() > TL_90) {
          std::cout << "3" << std::endl;
          get_reward();
          continue;
        }
        auto[u,v] = p_road;
        const ll exp_reward = cnt[u.i][u.j][v.i][v.j] * (TERM - t) * FEE_HIGHWAY;
        ll build_cost = get_cost_build_highway();

        if(exp_reward >= get_cost_build_highway() && money >= build_cost) {
          #ifdef LOCAL 
          fprintf(stderr,
            "[Info] BUILDING HIGHWAY!\n"
          );
          fprintf(stderr,
            "...... EXPECTED REWARD: %10lld, BUILD COST: %10lld\n\n", exp_reward, build_cost
          );
          #endif

          std::cout << "1 " << u.i + 1 << " " << u.j + 1 << " " << v.i + 1  << " " << v.j + 1 << std::endl;
          is_highway[u.i][u.j][v.i][v.j] = is_highway[v.i][v.j][u.i][u.j] = true;
          money -= build_cost;
          num_highway++;
          update_cnt();

        } else {
          
          std::cout << "3" << std::endl;
          money += DONATION;

        }

      } 

      get_reward();
    }

  } // solve

  void update_cnt() {

    cnt.clear();
    cnt.resize(H, Vec<Vec<Vec<int>>>(W, Vec<Vec<int>>(H, Vec<int>(W, 0))));

    // dijkstra
    Vec<Vec<double>> dist;

    for(int i = 0; i < N; i++) {

      dist.clear();
      dist.resize(H, Vec<double>(W, 1e19));

      if(A[i] == C[i]) continue;

      std::priority_queue<pair<double, Point>, vector<pair<double, Point>>, greater<pair<double,Point>> > pq;
      dist[A[i].i][A[i].j] = 0.0;
      pq.push({0.0, A[i]});
      int ni, nj;
      double len;

      while(!pq.empty()) {

        auto[cost, p] = pq.top(); pq.pop();

        if(cost - dist[p.i][p.j] > EPS || cost > dist[C[i].i][C[i].j] + EPS) continue;

        for(int d = 0; d < 4; d++) {

          ni = p.i + di[d];
          nj = p.j + dj[d];

          if(is_out(ni,nj,H,W)) continue;

          len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0;

          if(dist[ni][nj] > cost+len+EPS) {

            dist[ni][nj] = cost + len;
            pq.push(std::make_pair(cost+len, Point{ni,nj}));

          }

        }

      } // while

      dist_cur[i] = dist;

      Vec<Vec<bool>> visited(H, Vec<bool>(W, false));
      bool ok = false;
      int num_hw = 0;

      auto dfs=[&](auto dfs, const Point& u, const Point& v) -> void {
        if(visited[u.i][u.j] || ok) return;
        visited[u.i][u.j] = true;

        if(u==v) {
          ok = true;
          return;
        }

        for(int d = 0; d < 4; d++) {
          ni = u.i + di[d];
          nj = u.j + dj[d];
          if(is_out(ni,nj,H,W)) continue;

          double len = is_highway[ni][nj][u.i][u.j] ? TIME_HIGHWAY : 1.0; 
          if(abs((dist[u.i][u.j]-len)-dist[ni][nj]) < EPS) {
            if(is_highway[ni][nj][u.i][u.j]) num_hw++;
            if(!ok) dfs(dfs, Point{ni,nj}, v);
          }
        }
      };

      dfs(dfs, C[i], A[i]);

      num_highway_on_path[i] = num_hw;

      // 復元
      queue<pair<double,Point>> q_rev;
      q_rev.push({dist[C[i].i][C[i].j], C[i]});
      visited.clear();
      visited.resize(H, Vec<bool>(W, false));
      visited[C[i].i][C[i].j] = true;

      while(!q_rev.empty()) {

        auto[d, p] = q_rev.front(); q_rev.pop();
        
        for(int dir = 0; dir < 4; dir++) {

          ni = p.i + di[dir];
          nj = p.j + dj[dir];
          if(is_out(ni,nj,H,W)) continue;

          len = is_highway[p.i][p.j][ni][nj] ? TIME_HIGHWAY : 1.0;
          if(std::abs(dist[ni][nj] - (d - len)) < EPS) {
            cnt[ni][nj][p.i][p.j]++;
            cnt[p.i][p.j][ni][nj]++;

            if(!visited[ni][nj]) {
              visited[ni][nj] = true;
              q_rev.push(std::make_pair(d-len, Point{ni,nj}));
            }

          }
        }
      }


    }

    int max_cnt = -1;
    rep(i, 0, H)rep(j,0,W)rep(k,0,H)rep(l,0,W) if(cnt[i][j][k][l]>max_cnt&&!is_highway[i][j][k][l]){
      max_cnt=cnt[i][j][k][l];
      p_road = {Point{i,j}, Point{k,l}};
    }

  }

  void get_reward() {
    num_reward = 0;
    for(int i = 0; i < N; i++) {
      money += num_highway_on_path[i] * FEE_HIGHWAY;
      num_reward += num_highway_on_path[i];
    }
  }



  ll get_cost_build_highway() {

    constexpr double BASE = 1e7;
    return (ll)std::floor( BASE / std::sqrt(patron) );

  }

  // return summaries of solve
  void summary() {
    
    std::cerr << "\n##### SUMMARY #######################\n";
    fprintf(stderr, "ELAPSED TIME     : %6.4f s\n", get_time());
    fprintf(stderr, "NUMBER OF SEARCH : \n", this->num_search);
    std::cerr << "######################################\n";

  }

  
private:

};


int main(int argv, char* argc[]) {
  start_time = clock();
  Solver solver;

  #ifdef _OPTUNA
  bool ok = arg_parse(int argv, char* argc[])
  #endif

  solver.init();
  solver.solve();
  solver.summary();
  return 0;
}