結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 ogawakun
|
| 提出日時 | 2023-04-29 16:11:36 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,585 bytes |
| コンパイル時間 | 5,171 ms |
| コンパイル使用メモリ | 272,084 KB |
| 実行使用メモリ | 37,160 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-29 16:11:57 |
| 合計ジャッジ時間 | 12,510 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | -- | - |
ソースコード
#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++;
cout.flush();
continue;
}
// 足りない場合は資金集め
if (u < (ll)(1e7 / (long double)sqrt(v))) {
cout << 3 << endl;
u += 50000;
cout.flush();
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;
cout.flush();
} else {
cout << 3 << endl;
u += 50000;
cout.flush();
flag = 0;
}
} else {
cout << 3 << endl;
u += 50000;
cout.flush();
continue;
}
}
}