結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 nrvft
|
| 提出日時 | 2023-04-29 16:24:25 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 90 ms / 2,000 ms |
| コード長 | 7,802 bytes |
| コンパイル時間 | 4,009 ms |
| コンパイル使用メモリ | 230,408 KB |
| 実行使用メモリ | 24,480 KB |
| スコア | 6,417,360,898 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2023-04-29 16:26:12 |
| 合計ジャッジ時間 | 11,866 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma region MACRO#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;using vl = vector<ll>;template <class T>using vc = vector<T>;template <class T>using vvc = vector<vector<T>>;#define eb emplace_back#define all(x) (x).begin(), (x).end()#define rep(i, n) for (ll i = 0; i < (n); i++)#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)#define repe(i, l, r) for (ll i = (l); i < (r); i++)#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)#define repa(i, n) for (auto &i : n)template <class T1, class T2>inline bool chmax(T1 &a, const T2 &b) {if (a < b) {a = b;return 1;}return 0;}template <class T1, class T2>inline bool chmin(T1 &a, const T2 &b) {if (b < a) {a = b;return 1;}return 0;}struct init {init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(15);}} init_;template <typename T, typename U>ostream &operator<<(ostream &out, const pair<T, U> &a) { return out << a.first << ' ' << a.second; }template <typename T>ostream &operator<<(ostream &out, const vector<T> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << ' ';}return out;}template <typename T, size_t N>ostream &operator<<(ostream &out, const array<T, N> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << ' ';}return out;}template <typename T>ostream &operator<<(ostream &out, const set<T> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << ' ';}return out;}template <typename T, typename U>ostream &operator<<(ostream &out, const map<T, U> &a) {for (auto it = a.begin(); it != a.end();) {out << *it;if (++it != a.end()) out << '\n';}return out;}#ifdef DEBUGtemplate <class T, class N>void verr(const vector<T> &a, const N &n) {rep(i, n) cerr << a[i] << " ";cerr << endl;}template <class T, class N, size_t AN>void verr(const array<T, AN> &a, const N &n) {rep(i, n) cerr << a[i] << " ";cerr << endl;}ll dbgt = 1;void err() { cerr << "passed " << dbgt++ << endl; }template <class H, class... T>void err(H &&h, T &&...t) {cerr << h << (sizeof...(t) ? " " : "\n") << flush;if (sizeof...(t) > 0) err(forward<T>(t)...);}#elsevoid err() {}template <class H, class... T>void err(H &&h, T &&...t) {}template <class H, class... T>void verr(H &&h, T &&...t) {}#endifconst ll INF = 4e18;const ld EPS = 1e-11;const ld PI = acos(-1.0L);// const ll MOD = 1e9 + 7;const ll MOD = 998244353;//--------------------------------------------------------------------------------//inline uint32_t pcg32() {static uint64_t x = 0x0123456789012345u;unsigned count = (unsigned)(x >> 61);x *= 3;x ^= x >> 22;return (uint32_t)(x >> (22 + count));}#pragma endregion// 時間を出力chrono::system_clock::time_point startTime, endTime;// 経過時間(ms) を取得int get_diff_time() {return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - startTime).count();}// [0, a)の整数乱数inline int get_randint(int a) {return pcg32() % a;}// [0, 1]の乱数inline double get_randdouble() {return pcg32() / (double)numeric_limits<uint32_t>::max();}// 固定パラメータconstexpr int M = 14;constexpr int T = 400;constexpr int N = 3000;// ハイパーパラメータ ---------------------------------int ZERO = 0;double TIME_LIMIT = 1850; // msconstexpr int MAX_COLLABO = 36;constexpr int MAX_TURN = 240;enum hyper_param_idx {ZERO_ID,};int di[2] = {0, 1}, dj[2] = {1, 0};struct edge {int si, sj, ti, tj;int score;edge(){}edge(int si, int sj, int ti, int tj, int score): si(si), sj(sj), ti(ti), tj(tj), score(score){}edge(int si, int sj, int ti, int tj): si(si), sj(sj), ti(ti), tj(tj), score(0){}edge(int si, int sj, int d): si(si), sj(sj), ti(si + di[d]), tj(sj + dj[d]), score(0){}};int used[M][M][M][M];struct Solver {array<pair<int, int>, N> home, company;using Money = ll;vector<edge> es;queue<edge> qes;Solver() {}void solve() {input();init();greedy();output();}void greedy(){Money cur_money;int collabo;repe(t, 1, T + 1) {cin >> cur_money >> collabo;bool can_construct = (cur_money >= get_construct_money(collabo));if(can_construct) {construct_process(t, cur_money, collabo);} else {unconstruct_process(t, cur_money, collabo);}}}void construct_process(int turn, Money money, int collabo){if(turn > MAX_TURN) {cout << 3 << endl;return;}auto e = qes.front();while(used[e.si][e.sj][e.ti][e.tj]) {qes.pop();e = qes.front();}used[e.si][e.sj][e.ti][e.tj] = true;print(e);}void print(edge e) {cout << 1 << " " << e.si + 1 << " " << e.sj + 1 << " " << e.ti + 1 << " " << e.tj + 1 << endl;}void unconstruct_process(int turn, Money money, int collabo){if(collabo < MAX_COLLABO) {cout << 2 << endl;}else{cout << 3 << endl;}}int get_construct_money(int collabo) {return (int)(1e7 / sqrt(collabo));}void init(){rep(si, M) rep(sj, M) {rep(d, 2) {int ti = si + di[d], tj = sj + dj[d];if (ti >= M or tj >= M) continue;int score = 0;rep(i, N) {auto [i1, j1] = home[i];auto [i2, j2] = company[i];if (i1 > i2) swap(i1, i2);if (j1 > j2) swap(j1, j2);if (i1 <= si and ti <= i2 and j1 <= sj and tj <= j2) score++;}es.eb(si, sj, ti, tj, score);}}sort(all(es), [](edge a, edge b) { return a.score > b.score; });repa(e, es) {if(e.si != e.ti) {if(e.sj <= M / 2) {qes.emplace(e.si, e.sj, 0);qes.emplace(e.si, e.sj + 1, 1);qes.emplace(e.ti, e.sj, 0);} else {qes.emplace(e.si, e.sj - 1, 0);qes.emplace(e.si, e.sj - 1, 1);qes.emplace(e.ti, e.sj - 1, 0);}}else{if(e.si <= M / 2) {qes.emplace(e.si, e.sj, 1);qes.emplace(e.si + 1, e.sj, 0);qes.emplace(e.si, e.tj, 1);} else {qes.emplace(e.si - 1, e.sj, 1);qes.emplace(e.si - 1, e.sj, 0);qes.emplace(e.si - 1, e.tj, 1);}}}}void input() {int N_, T_;cin >> N_ >> T_;rep(i, N) {cin >> home[i].first >> home[i].second, home[i].first--, home[i].second--;cin >> company[i].first >> company[i].second, company[i].first--, company[i].second--;}}void output() {}};int main() {startTime = chrono::system_clock::now();#ifdef TUNE// params#endifSolver solver;solver.solve();}