結果
問題 | No.1779 Magical Swap |
ユーザー | hiro71687k |
提出日時 | 2023-08-28 22:35:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 3,520 bytes |
コンパイル時間 | 6,436 ms |
コンパイル使用メモリ | 266,824 KB |
実行使用メモリ | 10,984 KB |
最終ジャッジ日時 | 2023-08-28 22:36:37 |
合計ジャッジ時間 | 10,271 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
6,356 KB |
testcase_01 | AC | 19 ms
6,332 KB |
testcase_02 | AC | 27 ms
6,496 KB |
testcase_03 | AC | 21 ms
6,256 KB |
testcase_04 | AC | 99 ms
9,000 KB |
testcase_05 | AC | 54 ms
7,316 KB |
testcase_06 | AC | 55 ms
7,528 KB |
testcase_07 | AC | 84 ms
8,668 KB |
testcase_08 | AC | 19 ms
6,264 KB |
testcase_09 | AC | 38 ms
7,056 KB |
testcase_10 | AC | 99 ms
9,296 KB |
testcase_11 | AC | 60 ms
7,876 KB |
testcase_12 | AC | 31 ms
7,032 KB |
testcase_13 | AC | 80 ms
8,364 KB |
testcase_14 | AC | 85 ms
9,488 KB |
testcase_15 | AC | 209 ms
10,984 KB |
testcase_16 | AC | 101 ms
9,460 KB |
testcase_17 | AC | 99 ms
6,296 KB |
testcase_18 | AC | 18 ms
6,252 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll mod=1000000007; ll inf=10099999999999990; struct Eratosthenes { // テーブル vector<bool> isprime; // 整数 i を割り切る最小の素数 vector<ll> minfactor; vector<ll>mobius; // コンストラクタで篩を回す Eratosthenes(ll N) : isprime(N+1, true), minfactor(N+1, -1), mobius(N+1,1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (ll p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; mobius[p]=-1; // p 以外の p の倍数から素数ラベルを剥奪 for (ll q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; if ((q / p) % p == 0) mobius[q] = 0; else mobius[q] = -mobius[q]; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector<pair<ll,ll>> factorize(ll n) { vector<pair<ll,ll>> res; while (n > 1) { ll p = minfactor[n]; ll exp = 0; // n で割り切れる限り割る while (minfactor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } return res; } vector<ll>divisors(ll n){ vector<ll>res({1}); auto pf=factorize(n); for (auto p : pf) { ll s=(ll)res.size(); for (ll i = 0; i < s; i++) { ll v=1; for (ll j = 0; j < p.second; j++) { v*=p.first; res.push_back(res[i]*v); } } } return res; } }; int main(){ ll t; cin >> t; vector<string>ans; Eratosthenes er(200000); for (ll o = 0; o < t; o++) { ll n; cin >> n; vector<ll>a(n),b(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } for (ll i = 0; i < n; i++) { cin >> b[i]; } vector<ll>aa=a,bb=b; sort(aa.begin(),aa.end()); sort(bb.begin(),bb.end()); if (aa!=bb) { ans.push_back("No"); continue; } bool ok=true; for (ll i = 0; i < n; i++) { if (i==0) { if (a[i]!=b[i]) { ok=false; break; } }else if (er.isprime[i+1]&&(i+1)*2>n) { if (a[i]!=b[i]) { ok=false; break; } } } if (ok) { ans.push_back("Yes"); }else{ ans.push_back("No"); } } for (ll i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } }