結果
問題 | No.1460 Max of Min |
ユーザー | 沙耶花 |
提出日時 | 2021-03-31 22:56:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,150 ms / 2,000 ms |
コード長 | 4,235 bytes |
コンパイル時間 | 4,351 ms |
コンパイル使用メモリ | 269,664 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-05-09 09:45:58 |
合計ジャッジ時間 | 72,248 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 1,092 ms
6,944 KB |
testcase_07 | AC | 1,094 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 979 ms
6,944 KB |
testcase_11 | AC | 1,105 ms
6,944 KB |
testcase_12 | AC | 226 ms
6,944 KB |
testcase_13 | AC | 1,014 ms
6,944 KB |
testcase_14 | AC | 330 ms
6,944 KB |
testcase_15 | AC | 144 ms
6,944 KB |
testcase_16 | AC | 933 ms
6,944 KB |
testcase_17 | AC | 559 ms
6,940 KB |
testcase_18 | AC | 13 ms
6,940 KB |
testcase_19 | AC | 443 ms
6,944 KB |
testcase_20 | AC | 18 ms
6,940 KB |
testcase_21 | AC | 60 ms
6,944 KB |
testcase_22 | AC | 472 ms
6,940 KB |
testcase_23 | AC | 10 ms
6,940 KB |
testcase_24 | AC | 638 ms
6,940 KB |
testcase_25 | AC | 9 ms
6,944 KB |
testcase_26 | AC | 1,060 ms
6,944 KB |
testcase_27 | AC | 169 ms
6,944 KB |
testcase_28 | AC | 42 ms
6,944 KB |
testcase_29 | AC | 605 ms
6,944 KB |
testcase_30 | AC | 996 ms
6,940 KB |
testcase_31 | AC | 532 ms
6,940 KB |
testcase_32 | AC | 779 ms
6,944 KB |
testcase_33 | AC | 293 ms
6,940 KB |
testcase_34 | AC | 409 ms
6,944 KB |
testcase_35 | AC | 156 ms
6,940 KB |
testcase_36 | AC | 51 ms
6,944 KB |
testcase_37 | AC | 575 ms
6,944 KB |
testcase_38 | AC | 922 ms
6,944 KB |
testcase_39 | AC | 343 ms
6,940 KB |
testcase_40 | AC | 210 ms
6,944 KB |
testcase_41 | AC | 159 ms
6,940 KB |
testcase_42 | AC | 83 ms
6,940 KB |
testcase_43 | AC | 514 ms
6,944 KB |
testcase_44 | AC | 764 ms
6,940 KB |
testcase_45 | AC | 24 ms
6,944 KB |
testcase_46 | AC | 370 ms
6,944 KB |
testcase_47 | AC | 503 ms
6,940 KB |
testcase_48 | AC | 941 ms
6,944 KB |
testcase_49 | AC | 711 ms
6,944 KB |
testcase_50 | AC | 37 ms
6,940 KB |
testcase_51 | AC | 510 ms
6,940 KB |
testcase_52 | AC | 119 ms
6,944 KB |
testcase_53 | AC | 589 ms
6,944 KB |
testcase_54 | AC | 1,133 ms
6,940 KB |
testcase_55 | AC | 1,122 ms
6,944 KB |
testcase_56 | AC | 1,116 ms
6,940 KB |
testcase_57 | AC | 1,097 ms
6,940 KB |
testcase_58 | AC | 1,098 ms
6,940 KB |
testcase_59 | AC | 1,101 ms
6,944 KB |
testcase_60 | AC | 1,091 ms
6,944 KB |
testcase_61 | AC | 1,102 ms
6,944 KB |
testcase_62 | AC | 1,096 ms
6,940 KB |
testcase_63 | AC | 1,091 ms
6,940 KB |
testcase_64 | AC | 1,116 ms
6,944 KB |
testcase_65 | AC | 1,118 ms
6,944 KB |
testcase_66 | AC | 1,098 ms
6,944 KB |
testcase_67 | AC | 1,102 ms
6,940 KB |
testcase_68 | AC | 1,140 ms
6,944 KB |
testcase_69 | AC | 1,117 ms
6,940 KB |
testcase_70 | AC | 1,150 ms
6,940 KB |
testcase_71 | AC | 1,149 ms
6,940 KB |
testcase_72 | AC | 1,146 ms
6,940 KB |
testcase_73 | AC | 1,149 ms
6,940 KB |
testcase_74 | AC | 1,079 ms
6,940 KB |
testcase_75 | AC | 1,086 ms
6,944 KB |
testcase_76 | AC | 1,074 ms
6,944 KB |
testcase_77 | AC | 1,085 ms
6,940 KB |
testcase_78 | AC | 1,079 ms
6,940 KB |
testcase_79 | AC | 1,113 ms
6,940 KB |
testcase_80 | AC | 1,083 ms
6,940 KB |
testcase_81 | AC | 1,080 ms
6,944 KB |
testcase_82 | AC | 1,067 ms
6,940 KB |
testcase_83 | AC | 1,072 ms
6,940 KB |
testcase_84 | AC | 1,069 ms
6,944 KB |
testcase_85 | AC | 1,075 ms
6,940 KB |
testcase_86 | AC | 1,076 ms
6,940 KB |
testcase_87 | AC | 1,086 ms
6,940 KB |
testcase_88 | AC | 1,107 ms
6,944 KB |
testcase_89 | AC | 1,093 ms
6,944 KB |
testcase_90 | AC | 1,082 ms
6,940 KB |
testcase_91 | AC | 1,117 ms
6,940 KB |
testcase_92 | AC | 1,118 ms
6,940 KB |
testcase_93 | AC | 1,090 ms
6,944 KB |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000001 template<typename T> struct Kitamasa{ const int k; const vector<T> a, c; Kitamasa(const vector<T> &a, const vector<T> &c): k(a.size()), a(a), c(c) {} T solve(long long n){ T res = 0; auto d = cal(n); for(int i = 0; i < k; i++) res += d[i] * a[i]; return res; } private: vector<T> p1(const vector<T> &x){ /* a_n = sum(x_i * a_i) のとき、 a_n+1 = sum(y_i * a_i) となるyを求める a_n+1 = sum(x_i * a_i+1) = sum(x_i * a_i+1) + x_k-1*a_k = sum(x_i * a_i+1) + x_k-1*sum(c_i * a_i) //*/ vector<T> res(k); res[0] = x[k-1] * c[0]; for(int i = 1; i < k; i++){ res[i] = x[i-1] + (x[k-1] * c[i]); } return res; } vector<T> sq(const vector<T> &x){ /* a_n = sum(x_i * a_i) のとき、 a_2n = sum(y_i * a_i) となるyを求める a_2n = sum(x_i * a_n+i) ここで、 f(n) = x, f(n+1) = p1(f(n)), ... , f(n+k-1) が列挙できたとすると a_n+i = sum(f(n+i)_j * a_j) となる よって、 a_2n = sum(x_i*sum(f(n+i)_j * a_j)) //*/ vector<T> res(k); auto d = x; for(int i = 0; i < k; i++){ for(int j = 0; j < k; j++){ res[j] += x[i] * d[j]; } d = p1(d); } return res; } vector<T> cal(long long n){ vector<T> res(k); res[0] = 1; for(int i = 62; i >= 0; i--){ res = sq(res); if(n & (1ll << i)) res = p1(res); } return res; } }; template< int mod > struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { x |= p.x; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x &= p.x; return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); } static int get_mod() { return mod; } }; constexpr int MOD = 2; using mint = ModInt< MOD >; using VM = vector<mint>; using VVM = vector<VM>; int solve(long long nn,long long kk,vector<long long> aa,vector<long long> bb){ int k = kk; long long n= nn; VM a(k, 1), c(k, 1); rep(i,k){ a[i] = aa[i]; c[i] = bb[i]; } Kitamasa kita(a, c); return kita.solve(n).x; } int main(){ int K; long long N; cin>>K>>N; vector<long long> A(K),B(K); rep(i,K){ cin>>A[i]; } rep(i,K){ cin>>B[i]; } vector<long long> X; rep(i,K){ X.push_back(A[i]); X.push_back(B[i]); } sort(X.begin(),X.end()); X.erase(unique(X.begin(),X.end()),X.end()); long long ok = 0,ng = X.size(); while(ng-ok>1LL){ long long mid = (ok+ng)/2; vector<long long> a(K),b(K); rep(i,K){ if(A[i]<X[mid]){ a[i] = 0; } else{ a[i] = 1; } if(B[i]<X[mid]){ b[i] = 0; } else{ b[i] = 1; } } if(solve(N,K,a,b)==1)ok = mid; else ng = mid; } cout<<X[ok]<<endl; return 0; }