結果

問題 No.5016 Worst Mayor
ユーザー 7iz67iz6
提出日時 2023-04-29 15:44:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 626 ms / 2,000 ms
コード長 10,976 bytes
コンパイル時間 4,222 ms
コンパイル使用メモリ 207,460 KB
実行使用メモリ 26,940 KB
スコア 6,256,128,750
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:44:51
合計ジャッジ時間 38,066 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 584 ms
26,940 KB
testcase_01 AC 574 ms
26,772 KB
testcase_02 AC 581 ms
26,836 KB
testcase_03 AC 571 ms
26,684 KB
testcase_04 AC 593 ms
26,544 KB
testcase_05 AC 592 ms
26,284 KB
testcase_06 AC 572 ms
26,828 KB
testcase_07 AC 613 ms
26,404 KB
testcase_08 AC 584 ms
26,292 KB
testcase_09 AC 596 ms
26,828 KB
testcase_10 AC 568 ms
26,888 KB
testcase_11 AC 556 ms
26,808 KB
testcase_12 AC 626 ms
26,440 KB
testcase_13 AC 540 ms
26,384 KB
testcase_14 AC 585 ms
26,440 KB
testcase_15 AC 589 ms
26,840 KB
testcase_16 AC 567 ms
26,580 KB
testcase_17 AC 580 ms
26,556 KB
testcase_18 AC 585 ms
26,696 KB
testcase_19 AC 590 ms
26,176 KB
testcase_20 AC 595 ms
26,240 KB
testcase_21 AC 566 ms
26,056 KB
testcase_22 AC 587 ms
26,780 KB
testcase_23 AC 574 ms
26,420 KB
testcase_24 AC 587 ms
26,116 KB
testcase_25 AC 511 ms
26,360 KB
testcase_26 AC 586 ms
26,812 KB
testcase_27 AC 582 ms
26,136 KB
testcase_28 AC 605 ms
26,308 KB
testcase_29 AC 586 ms
26,848 KB
testcase_30 AC 588 ms
26,104 KB
testcase_31 AC 590 ms
26,156 KB
testcase_32 AC 598 ms
26,916 KB
testcase_33 AC 609 ms
26,220 KB
testcase_34 AC 587 ms
26,284 KB
testcase_35 AC 569 ms
26,916 KB
testcase_36 AC 538 ms
26,712 KB
testcase_37 AC 581 ms
26,448 KB
testcase_38 AC 577 ms
26,124 KB
testcase_39 AC 565 ms
26,768 KB
testcase_40 AC 570 ms
26,692 KB
testcase_41 AC 566 ms
26,248 KB
testcase_42 AC 567 ms
26,896 KB
testcase_43 AC 614 ms
26,144 KB
testcase_44 AC 585 ms
26,564 KB
testcase_45 AC 589 ms
26,364 KB
testcase_46 AC 595 ms
26,872 KB
testcase_47 AC 553 ms
26,440 KB
testcase_48 AC 606 ms
26,412 KB
testcase_49 AC 602 ms
26,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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_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
      cin >> nil >> nil;
      #endif

      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\n", num_highway
        );
      }

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

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

      } else if(t < 360){

        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) {
          
          fprintf(stderr,
            "[Info] BUILDING HIGHWAY!\n"
          );
          fprintf(stderr,
            "...... EXPECTED REWARD: %10lld, BUILD COST: %10lld\n\n", exp_reward, build_cost
          );

          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;

        }

      } 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++) {
          int ni = u.i + di[d];
          int 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_highway++;
            if(!ok) dfs(dfs, Point{ni,nj}, v);
          }
        }
      };

      dfs(dfs, A[i], C[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[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() {
    for(int i = 0; i < N; i++) money += num_highway_on_path[i] * FEE_HIGHWAY;
  }



  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 : ", 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;
}
0