結果

問題 No.5016 Worst Mayor
ユーザー nrvftnrvft
提出日時 2023-04-29 16:03:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 7,801 bytes
コンパイル時間 3,891 ms
コンパイル使用メモリ 230,840 KB
実行使用メモリ 24,384 KB
スコア 4,441,427,332
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 16:04:01
合計ジャッジ時間 10,989 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
24,000 KB
testcase_01 AC 87 ms
23,712 KB
testcase_02 AC 88 ms
24,372 KB
testcase_03 AC 87 ms
23,568 KB
testcase_04 AC 89 ms
23,388 KB
testcase_05 AC 85 ms
23,856 KB
testcase_06 AC 88 ms
24,000 KB
testcase_07 AC 88 ms
24,336 KB
testcase_08 AC 87 ms
24,384 KB
testcase_09 AC 88 ms
23,460 KB
testcase_10 AC 87 ms
23,424 KB
testcase_11 AC 88 ms
23,844 KB
testcase_12 AC 90 ms
23,448 KB
testcase_13 AC 90 ms
24,360 KB
testcase_14 AC 89 ms
24,012 KB
testcase_15 AC 87 ms
23,556 KB
testcase_16 AC 90 ms
24,384 KB
testcase_17 AC 88 ms
24,336 KB
testcase_18 AC 89 ms
23,664 KB
testcase_19 AC 89 ms
24,384 KB
testcase_20 AC 87 ms
24,012 KB
testcase_21 AC 89 ms
23,544 KB
testcase_22 AC 90 ms
23,988 KB
testcase_23 AC 88 ms
23,580 KB
testcase_24 AC 87 ms
23,988 KB
testcase_25 AC 89 ms
24,024 KB
testcase_26 AC 88 ms
23,676 KB
testcase_27 AC 87 ms
23,556 KB
testcase_28 AC 88 ms
23,556 KB
testcase_29 AC 88 ms
24,000 KB
testcase_30 AC 87 ms
23,376 KB
testcase_31 AC 86 ms
23,628 KB
testcase_32 AC 88 ms
23,616 KB
testcase_33 AC 87 ms
23,448 KB
testcase_34 AC 84 ms
23,544 KB
testcase_35 AC 89 ms
23,628 KB
testcase_36 AC 87 ms
23,628 KB
testcase_37 AC 88 ms
23,460 KB
testcase_38 AC 83 ms
23,856 KB
testcase_39 AC 86 ms
23,388 KB
testcase_40 AC 87 ms
24,060 KB
testcase_41 AC 89 ms
24,012 KB
testcase_42 AC 88 ms
23,688 KB
testcase_43 AC 87 ms
24,372 KB
testcase_44 AC 88 ms
23,448 KB
testcase_45 AC 85 ms
23,652 KB
testcase_46 AC 89 ms
24,096 KB
testcase_47 AC 86 ms
23,448 KB
testcase_48 AC 87 ms
24,372 KB
testcase_49 AC 88 ms
24,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 DEBUG
template <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)...);
}
#else
void err() {}
template <class H, class... T>
void err(H &&h, T &&...t) {}
template <class H, class... T>
void verr(H &&h, T &&...t) {}
#endif

const 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; // ms
constexpr int MAX_COLLABO = 36;
constexpr int MAX_TURN = 320;

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
#endif
    Solver solver;
    solver.solve();
}
0