結果

問題 No.5016 Worst Mayor
コンテスト
ユーザー ogawakun
提出日時 2023-04-29 16:17:51
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,475 bytes
コンパイル時間 5,906 ms
コンパイル使用メモリ 271,644 KB
実行使用メモリ 37,780 KB
スコア 0
最終ジャッジ日時 2023-04-29 16:18:50
合計ジャッジ時間 12,718 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using namespace chrono;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<P> vP;
typedef vector<string> vs;
typedef vector<vi> vvi;
#define rep(i, l, n) for (ll i = (ll)(l); i < (ll)(n); i++)
#define repd(i, n, l) for (ll i = (ll)(n); i > (ll)(l); i--)
#define Copy(from, to) copy(from.begin(), from.end(), to.begin())
#define Sort(a) sort(a.begin(), a.end())
#define gSort(a) sort(a.begin(), a.end(), greater())
#define Unique(a) sort(a.begin(), a.end())
template <class T, class S> inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S> inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}
#define dPQ priority_queue<ll, vll, greater<ll>>
#define PQ priority_queue<ll, vll>
#define INF INT_MAX
#define INFF (9223372036854775800)
#define TIME_LIMIT (5.96)
#define def (201010)
// #define MOD (1000000007)
#define MOD (998244353)
#define PI (3.14159265359)

ll N, T;
vll A, B, C, D;

// ll calc_gain(map<P, int> &highway) {
//   ll ret = 0;
//   rep(i, 0, N) {
//     vvi dp(14, vi(14, 0));
//     ll from = B[i] <= D[i] ? A[i] * 14 + B[i] : C[i] * 14 + D[i];
//     ll to = B[i] > D[i] ? A[i] * 14 + B[i] : C[i] * 14 + D[i];
//     // 左上→右下
//     if (from / 14 < to / 14) {
//       rep(h, from / 14, to / 14 + 1) {
//         rep(w, from % 14, to % 14 + 1) {
//           if (h == from / 14 && w == from % 14)
//             continue;
//           ll mi = min(h * 14 + w - 1, h * 14 + w);
//           ll ma = max(h * 14 + w - 1, h * 14 + w);
//           if (w != 0)
//             chmax(dp[h][w], dp[h][w - 1] + highway[{mi, ma}]);
//           mi = min((h - 1) * 14 + w, h * 14 + w);
//           ma = max((h - 1) * 14 + w, h * 14 + w);
//           if (h != 0)
//             chmax(dp[h][w], dp[h - 1][w] + highway[{mi, ma}]);
//         }
//       }
//     }
//     // 左下→右上
//     else {
//       repd(h, from / 14, to / 14 - 1) {
//         rep(w, from % 14, to % 14 + 1) {
//           if (h == from / 14 && w == from % 14)
//             continue;
//           ll mi = min(h * 14 + w - 1, h * 14 + w);
//           ll ma = max(h * 14 + w - 1, h * 14 + w);
//           if (w != 0)
//             chmax(dp[h][w], dp[h][w - 1] + highway[{mi, ma}]);
//           mi = min((h + 1) * 14 + w, h * 14 + w);
//           ma = max((h + 1) * 14 + w, h * 14 + w);
//           if (h != 13)
//             chmax(dp[h][w], dp[h + 1][w] + highway[{mi, ma}]);
//         }
//       }
//     }

//     ret += 60 * dp[to / 14][to % 14];
//   }
//   // cout << ret / 60 << endl;
//   return ret;
// }

ll calc_gain(map<P, int> &highway) {
  ll ret = 0;
  rep(i, 0, N) {
    for (auto cu : highway) {
      if (cu.second == 0)
        continue;
      ll mih = min(cu.first.first / 14, cu.first.second / 14);
      ll mah = max(cu.first.first / 14, cu.first.second / 14);
      ll miw = min(cu.first.first % 14, cu.first.second % 14);
      ll maw = max(cu.first.first % 14, cu.first.second % 14);
      if (min(A[i], C[i]) <= mih && mah <= max(A[i], C[i]) &&
          min(B[i], D[i]) <= miw && maw <= max(B[i], D[i]))
        ret += 60;
    }
  }

  return ret;
}

int main() {
  cin >> N >> T;
  rep(i, 0, N) A.resize(N), B.resize(N), C.resize(N), D.resize(N);
  rep(i, 0, N) cin >> A[i] >> B[i] >> C[i] >> D[i];
  rep(i, 0, N) A[i]--, B[i]--, C[i]--, D[i]--;

  map<P, int> highway;
  bool flag = 1;
  // ll u = 1000000, v = 1;
  rep(i, 0, T) {
    ll u, v;
    cin >> u >> v;
    if (u == -1 && v == -1)
      return 0;

    // 初めは協力者
    if (v <= 99) {
      cout << 2 << endl;
      v++;
      continue;
    }

    // 足りない場合は資金集め
    if (u < (ll)(1e7 / (long double)sqrt(v))) {
      cout << 3 << endl;
      u += 50000;
      continue;
    }

    if (flag) {
      P best_way = {-1, -1};
      ll best_score = (T - i) * 50000 +
                      (ll)(1e7 / (long double)sqrt(v)) / max((ll)1, (200 - i));
      ll unit_gain = calc_gain(highway);
      rep(from, 0, 14 * 14 - 1) {
        rep(dir, 0, 2) {
          ll to = from;
          if (dir == 0) {
            if (to % 14 != 13)
              to++;
            else
              continue;
          }
          if (dir == 1) {
            if (to / 14 != 13)
              to += 14;
            else
              continue;
          }

          if (highway[{from, to}] == 1)
            continue;
          // cout << "a" << from / 14 << " " << from % 14 << " -> " << to / 14
          // << " "
          //      << to % 14 << " ";
          highway[{from, to}] = 1;
          ll predict_unit_gain = calc_gain(highway);
          // cout << predict_unit_gain << endl;
          if (best_score < (predict_unit_gain - unit_gain) * (T - i)) {
            best_score = (predict_unit_gain - unit_gain) * (T - i);
            best_way = {from, to};
          }
          highway.erase({from, to});
        }
      }

      if (best_way.first != -1) {
        highway[best_way] = 1;
        cout << 1 << " " << best_way.first / 14 + 1 << " "
             << best_way.first % 14 + 1 << " " << best_way.second / 14 + 1
             << " " << best_way.second % 14 + 1 << endl;
      } else {
        cout << 3 << endl;
        u += 50000;
        flag = 0;
      }
    } else {
      cout << 3 << endl;
      u += 50000;
      continue;
    }
  }
}
0