結果

問題 No.5016 Worst Mayor
ユーザー ogawakunogawakun
提出日時 2023-04-29 16:39:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,645 ms / 2,000 ms
コード長 5,814 bytes
コンパイル時間 4,840 ms
コンパイル使用メモリ 270,296 KB
実行使用メモリ 24,348 KB
スコア 5,438,959,620
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 16:40:41
合計ジャッジ時間 70,629 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,592 ms
23,424 KB
testcase_01 AC 1,627 ms
24,012 KB
testcase_02 AC 1,634 ms
24,036 KB
testcase_03 AC 1,104 ms
23,640 KB
testcase_04 AC 1,614 ms
23,496 KB
testcase_05 AC 1,099 ms
23,400 KB
testcase_06 AC 960 ms
23,844 KB
testcase_07 AC 1,599 ms
23,928 KB
testcase_08 AC 1,255 ms
23,652 KB
testcase_09 AC 1,600 ms
23,916 KB
testcase_10 AC 1,595 ms
24,024 KB
testcase_11 AC 552 ms
24,204 KB
testcase_12 AC 1,104 ms
23,892 KB
testcase_13 AC 1,267 ms
23,412 KB
testcase_14 AC 664 ms
23,232 KB
testcase_15 AC 109 ms
23,628 KB
testcase_16 AC 660 ms
23,568 KB
testcase_17 AC 965 ms
24,036 KB
testcase_18 AC 1,638 ms
23,712 KB
testcase_19 AC 1,597 ms
23,904 KB
testcase_20 AC 1,270 ms
23,280 KB
testcase_21 AC 1,093 ms
24,228 KB
testcase_22 AC 1,632 ms
23,892 KB
testcase_23 AC 1,622 ms
23,532 KB
testcase_24 AC 984 ms
23,532 KB
testcase_25 AC 1,607 ms
24,060 KB
testcase_26 AC 1,645 ms
23,400 KB
testcase_27 AC 671 ms
23,652 KB
testcase_28 AC 1,621 ms
24,036 KB
testcase_29 AC 1,635 ms
23,508 KB
testcase_30 AC 1,634 ms
24,000 KB
testcase_31 AC 357 ms
23,532 KB
testcase_32 AC 559 ms
23,916 KB
testcase_33 AC 356 ms
23,388 KB
testcase_34 AC 1,245 ms
23,376 KB
testcase_35 AC 580 ms
23,640 KB
testcase_36 AC 1,622 ms
24,216 KB
testcase_37 AC 1,616 ms
23,244 KB
testcase_38 AC 1,599 ms
23,388 KB
testcase_39 AC 1,607 ms
23,400 KB
testcase_40 AC 1,628 ms
24,228 KB
testcase_41 AC 460 ms
23,412 KB
testcase_42 AC 672 ms
23,436 KB
testcase_43 AC 1,588 ms
24,348 KB
testcase_44 AC 1,600 ms
23,280 KB
testcase_45 AC 666 ms
24,276 KB
testcase_46 AC 1,611 ms
23,412 KB
testcase_47 AC 1,599 ms
24,228 KB
testcase_48 AC 917 ms
23,904 KB
testcase_49 AC 1,112 ms
23,628 KB
権限があれば一括ダウンロードができます

ソースコード

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 (1.5)
#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) {
    auto ite = highway.begin();
    while (ite != highway.end()) {
      if (ite->second == 0) {
        highway.erase(ite++);
        continue;
      }
      
      ll mih = min(ite->first.first / 14, ite->first.second / 14);
      ll mah = max(ite->first.first / 14, ite->first.second / 14);
      ll miw = min(ite->first.first % 14, ite->first.second % 14);
      ll maw = max(ite->first.first % 14, ite->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;
      ite++;
    }
  }

  return ret;
}

double ela_times(system_clock::time_point &clock) {
  return duration_cast<microseconds>(system_clock::now() - clock).count() *
         1e-6;
}

int main() {
  auto startClock = system_clock::now();
  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 && ela_times(startClock) < TIME_LIMIT) {
      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