結果

問題 No.5016 Worst Mayor
ユーザー 7iz67iz6
提出日時 2023-04-29 14:55:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,984 bytes
コンパイル時間 5,624 ms
コンパイル使用メモリ 197,012 KB
実行使用メモリ 37,076 KB
スコア 0
最終ジャッジ日時 2023-04-29 14:55:25
合計ジャッジ時間 10,734 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

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<Vec<bool>>>> is_highway;
  Vec<pair<Point,Point>> highway_list;

  #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--;
    }

    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))));

    // 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++) {
      cin >> money >> patron;

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

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

      } else if(t < 360){

        auto[u,v] = p_road;
        const int exp_reward = cnt[u.i][u.j][v.i][v.j] * (TERM - t) * FEE_HIGHWAY;

        if(exp_reward >= get_cost_build_highway()) {

          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;
          update_cnt();

        } else {

          std::cout << "3" << std::endl;

        }

      }

    }

  } // 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

      // 復元
      queue<pair<double,Point>> q_rev;
      Vec<Vec<bool>> visited(H, Vec<bool>(W, false));
      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){
      max_cnt=cnt[i][j][k][l];
      p_road = {Point{i,j}, Point{k,l}};
    }


  }

  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