結果

問題 No.1779 Magical Swap
ユーザー nanophoto12nanophoto12
提出日時 2021-12-12 11:24:32
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 4,354 bytes
コンパイル時間 5,051 ms
コンパイル使用メモリ 273,984 KB
実行使用メモリ 10,144 KB
最終ジャッジ日時 2023-09-28 03:07:55
合計ジャッジ時間 9,089 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 2 ms
4,356 KB
testcase_02 AC 11 ms
4,376 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 73 ms
7,776 KB
testcase_05 AC 33 ms
5,168 KB
testcase_06 AC 37 ms
5,392 KB
testcase_07 AC 64 ms
7,016 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 23 ms
4,792 KB
testcase_10 AC 93 ms
9,684 KB
testcase_11 AC 49 ms
6,472 KB
testcase_12 AC 17 ms
4,376 KB
testcase_13 AC 72 ms
8,400 KB
testcase_14 AC 81 ms
10,144 KB
testcase_15 AC 238 ms
4,380 KB
testcase_16 AC 87 ms
8,660 KB
testcase_17 AC 87 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)

template<typename T>
static inline void chmin(T& ref, const T  value) {
	if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
	if (ref < value) ref = value;
}

#include <atcoder/all>

using namespace atcoder;

typedef modint998244353 mint;

typedef ll CHT_TYPE;

class ConvexHullTrickDynamic {
private:
	// 直線 **************************************************************
	struct Line {
		CHT_TYPE a, b; // y = ax + b
		mutable std::function<const Line* ()> getSuc; // 次の直線へのポインタ (ソートで用いる)

		bool operator<(const Line& rhs) const {
			// 取得クエリでは次の直線との差分でソート
			if (rhs.b == IS_QUERY) {
				const Line* suc = getSuc();
				if (suc == nullptr) return false;
				const CHT_TYPE& x = rhs.a;
				return (suc->a - a) * x + suc->b - b > 0;
			}
			if (b == IS_QUERY) {
				const Line* suc = rhs.getSuc();
				if (suc == nullptr) return true;
				const CHT_TYPE& x = a;
				return (suc->a - rhs.a) * x + suc->b - rhs.b < 0;
			}

			// 通常の直線どうしは傾きソート
			return a < rhs.a;
		}
	};

	// 直線集合 **********************************************************
	class LinesSet {
	private:
		// true -> 最小値クエリ, false -> 最大値クエリ
		bool flagMin;
		std::multiset<Line> lines;
	public:
		// コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
		LinesSet(bool flagMin = true) : flagMin(flagMin) {};

		// 直線lが不必要であるかどうか
		bool isBad(std::multiset<Line>::iterator l) {
			const auto&& nel = std::next(l);
			if (l == lines.begin()) { // lが傾き最小のとき
				if (nel == lines.end()) return false; // lしかないなら必要
				return l->a == nel->a && l->b <= nel->b;
			}
			else {
				const auto&& prl = std::prev(l);
				if (nel == lines.end()) return l->a == prl->a && l->b <= prl->b;
				return (prl->b - l->b) * (nel->a - l->a) >= (nel->b - l->b) * (prl->a - l->a);
			}
		}

		// 直線y=ax+bを追加する
		inline void add(CHT_TYPE a, CHT_TYPE b) {
			if (flagMin) a = -a, b = -b;
			auto&& it = lines.insert(Line{ a, b });
			it->getSuc = [=] { return (std::next(it) == lines.end() ? nullptr : &*std::next(it)); };
			if (isBad(it)) { lines.erase(it); return; }
			while (std::next(it) != lines.end() && isBad(std::next(it))) lines.erase(std::next(it));
			while (it != lines.begin() && isBad(std::prev(it))) lines.erase(std::prev(it));
		}

		// 直線群の中でxの時に最小(最大)となる値を返す
		inline CHT_TYPE get(CHT_TYPE x) {
			auto&& l = *lines.lower_bound(Line{ x, IS_QUERY });
			if (flagMin) return -l.a * x - l.b;
			else return l.a * x + l.b;
		}
	};

	static const CHT_TYPE IS_QUERY = std::numeric_limits<CHT_TYPE>::lowest();
	LinesSet linesSet;

public:
	// コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
	ConvexHullTrickDynamic(bool flagMin = true) : linesSet(flagMin) {}
	// 直線y=ax+bを追加する
	inline void add(CHT_TYPE a, CHT_TYPE b) { linesSet.add(a, b); }
	// あるxのときの直線集合での最小値を求める
	inline CHT_TYPE get(CHT_TYPE x) { return linesSet.get(x); }
};

int main() {
	ll t;
	cin >> t;
	rep(_, t) {
		ll n;
		cin >> n;
		vector<ll> as(n + 1, 0), bs(n + 1, 0);
		rep(i, n) {
			cin >> as[i + 1];
		}
		rep(i, n) {
			cin >> bs[i + 1];
		}
		atcoder::dsu tree(n + 1);
		for (int i = 2; i <= n; i++) {
			for (int j = 1; i * j <= n; j++) {
				tree.merge(i, i* j);
			}
		}
		vector<vector<ll>> ag, bg;
		bool ok = true;
		for(auto& x : tree.groups()){
			ag.emplace_back(); 
			bg.emplace_back();
			for (auto y : x) {
				ag.back().emplace_back(as[y]);
				bg.back().emplace_back(bs[y]);
			}
			sort(ag.back().begin(), ag.back().end());
			sort(bg.back().begin(), bg.back().end());
			if (ag.back() != bg.back()) {
				ok = false;
				break;
			}
		}
		if (ok) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	return 0;
}
0