#864394 (C++17(gcc12)) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: assy1028
• 提出日時: 2023-04-29 14:13:57
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 101 ms / 2,000 ms
• コード長: 3,467 bytes
• コンパイル時間: 2,450 ms
• コンパイル使用メモリ: 130,720 KB
• 実行使用メモリ: 24,288 KB
• スコア: 5,629,591,851
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2023-04-29 14:14:09
• 合計ジャッジ時間: 9,759 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

ファイルパターン	結果
other	AC * 50

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;
#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
    size_t seed = hash<T>()(x.first);
    return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int INF = 1e9 + 9;
//const ll INF = 1e18 + 9;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const double EPS = 1e-8;
const double PI = acos(-1);
unsigned long xor128(void) {
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
// [0, k)
int rand(int k) {
    return xor128() % k;
}
// [a, b)
int rand(int a, int b) {
    return a + xor128() % (b - a);
}
int n, t;
int a[3010], b[3010], c[3010], d[3010];
const int MAX_Y = 14;
const int MAX_X = 14;
int route_count[15][15][15][15];
struct road {
    int count, x, y, z, w;
};
bool operator< (const road& r1, const road& r2) {
    return r1.count < r2.count;
}
void build(const road& r) {
    cout << "1 " << r.x+1 << " " << r.y+1 << " " << r.z+1 << " " << r.w+1 << endl; cout.flush();
}
void get_coop() {
    cout << "2" << endl; cout.flush();
}
void get_money() {
    cout << "3" << endl; cout.flush();
}
void init() {
    for (int i = 0; i < n; i++) {
        const int minY = min(a[i], c[i]);
        const int maxY = max(a[i], c[i]);
        const int minX = min(b[i], d[i]);
        const int maxX = max(b[i], d[i]);
        for (int y = minY; y <= maxY; y++) {
            for (int x = minX; x <= maxX; x++) {
                if (y < maxY) route_count[y][x][y+1][x]++;
                if (x < maxX) route_count[y][x][y][x+1]++;
            }
        }
    }
}
void solve() {
    init();
    priority_queue<road> que;
    for (int y = 0; y < MAX_Y; y++) {
        for (int x = 0; x < MAX_X; x++) {
            if (y < MAX_Y-1) que.push({route_count[y][x][y+1][x], y, x, y+1, x});
            if (x < MAX_X-1) que.push({route_count[y][x][y][x+1], y, x, y, x+1});
        }
    }
    int u, v;
    for (int iter = 0; iter < t; iter++) {
        cin >> u >> v;
        const int cost = 1e7 / sqrt(v);
        const auto& r = que.top();
        const int gain = r.count * (t-iter) * 60;
        //cerr << "??? " << u << " " << v << " " << cost << " " << gain << endl;
        if (u < cost || gain < cost) {
            get_coop();
        } else {
            build(r);
            que.pop();
        }
    }
}
void input() {
    cin >> n >> t;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
        c[i]--;
        d[i]--;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    input();
    solve();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX