#864366 (C++17) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: square1001
• 提出日時: 2023-04-29 13:45:44
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 94 ms / 2,000 ms
• コード長: 1,406 bytes
• コンパイル時間: 1,360 ms
• コンパイル使用メモリ: 98,292 KB
• 実行使用メモリ: 24,336 KB
• スコア: 8,407,805,899
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2023-04-29 13:45:55
• 合計ジャッジ時間: 9,767 ms
• ジャッジサーバーID （参考情報）: judge14 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	94 ms; 23,820 KB
testcase_01	AC	87 ms; 24,300 KB
testcase_02	AC	86 ms; 23,424 KB
testcase_03	AC	87 ms; 23,412 KB
testcase_04	AC	88 ms; 23,844 KB
testcase_05	AC	91 ms; 23,640 KB
testcase_06	AC	87 ms; 24,024 KB
testcase_07	AC	87 ms; 23,412 KB
testcase_08	AC	86 ms; 23,976 KB
testcase_09	AC	88 ms; 23,436 KB
testcase_10	AC	82 ms; 24,216 KB
testcase_11	AC	87 ms; 24,288 KB
testcase_12	AC	88 ms; 24,228 KB
testcase_13	AC	86 ms; 24,264 KB
testcase_14	AC	87 ms; 24,264 KB
testcase_15	AC	87 ms; 23,700 KB
testcase_16	AC	90 ms; 24,024 KB
testcase_17	AC	86 ms; 23,376 KB
testcase_18	AC	89 ms; 23,412 KB
testcase_19	AC	88 ms; 24,276 KB
testcase_20	AC	87 ms; 24,048 KB
testcase_21	AC	87 ms; 24,252 KB
testcase_22	AC	87 ms; 23,664 KB
testcase_23	AC	88 ms; 23,820 KB
testcase_24	AC	87 ms; 24,036 KB
testcase_25	AC	88 ms; 23,412 KB
testcase_26	AC	87 ms; 23,364 KB
testcase_27	AC	88 ms; 23,376 KB
testcase_28	AC	87 ms; 23,424 KB
testcase_29	AC	87 ms; 23,376 KB
testcase_30	AC	87 ms; 24,300 KB
testcase_31	AC	87 ms; 24,192 KB
testcase_32	AC	84 ms; 24,264 KB
testcase_33	AC	87 ms; 23,544 KB
testcase_34	AC	83 ms; 24,060 KB
testcase_35	AC	85 ms; 24,336 KB
testcase_36	AC	87 ms; 24,048 KB
testcase_37	AC	91 ms; 24,180 KB
testcase_38	AC	89 ms; 23,424 KB
testcase_39	AC	87 ms; 23,568 KB
testcase_40	AC	87 ms; 23,412 KB
testcase_41	AC	86 ms; 24,300 KB
testcase_42	AC	87 ms; 23,640 KB
testcase_43	AC	86 ms; 23,580 KB
testcase_44	AC	87 ms; 24,324 KB
testcase_45	AC	87 ms; 24,240 KB
testcase_46	AC	88 ms; 24,024 KB
testcase_47	AC	89 ms; 23,556 KB
testcase_48	AC	87 ms; 24,036 KB
testcase_49	AC	86 ms; 23,400 KB

ソースコード

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	const int D = 14;
	int N, T;
	cin >> N >> T;
	vector<int> X(N), Y(N);
	for (int i = 0; i < N; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		X[i] = (a - 1) * D + (b - 1);
		Y[i] = (c - 1) * D + (d - 1);
	}
	vector<vector<int> > v;
	for (int i = 1; i <= D; i++) {
		for (int j = 1; j <= D; j++) {
			if (j != D) {
				v.push_back({i, j, i, j + 1});
			}
			if (i != D) {
				v.push_back({i, j, i + 1, j});
			}
		}
	}
	auto level = [](int x) {
		return __builtin_ctz(x);
	};
	auto dist = [](const vector<int>& v) {
		return abs(v[0] - 8) + abs(v[1] - 8) + abs(v[2] - 8) + abs(v[3] - 8);
	};
	sort(v.begin(), v.end(), [&](vector<int> vx, vector<int> vy) {
		int lx = max({level(vx[0]), level(vx[1]), level(vx[2]), level(vx[3])});
		int ly = max({level(vy[0]), level(vy[1]), level(vy[2]), level(vy[3])});
		if (lx != ly) return lx > ly;
		return dist(vx) < dist(vy);
	});
	int cur = 0;
	for (int i = 0; i < T; i++) {
		int a, b;
		cin >> a >> b;
		if (i < T / 4) {
			cout << 2 << endl;
		}
		else if (i < T * 3 / 4) {
			int req = int(10000000 / sqrt(b));
			if (a >= req) {
				cout << 1 << ' ' << v[cur][0] << ' ' << v[cur][1] << ' ' << v[cur][2] << ' ' << v[cur][3] << endl;
				cur += 1;
			}
			else {
				cout << 3 << endl;
			}
		}
		else {
			cout << 3 << endl;
		}
	}
	return 0;
}