結果

問題 No.5016 Worst Mayor
ユーザー 7iz67iz6
提出日時 2023-04-29 15:19:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 10,085 bytes
コンパイル時間 3,696 ms
コンパイル使用メモリ 197,964 KB
実行使用メモリ 24,492 KB
スコア 0
平均クエリ数 360.00
最終ジャッジ日時 2023-04-29 15:20:35
合計ジャッジ時間 33,990 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ
(要ログイン)

テストケース

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

ソースコード

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

    patron = 1;
    money = INIT_FUND;
    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++) {
      int null;
      scanf("%d %d", &null, &null);

      if(t % 40 == 0) {
        fprintf(stderr, 
          "[Info] time: %6.3f, money: %10d, patron: %2d\n", get_time(), money, patron
        );
      }

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

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

      } 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;
        ll build_cost = get_cost_build_highway();
        if(exp_reward >= get_cost_build_highway() && money >= 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;

          update_cnt_and_get_reward();

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

        }

      }

    }

  } // solve

  void update_cnt_and_get_reward() {

    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

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

      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]) money+=FEE_HIGHWAY;
            if(!ok) dfs(dfs, Point{ni,nj}, v);
          }
        }
      };

      // 復元
      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}};
    }


  }

  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