結果
問題 | No.1532 Different Products |
ユーザー | noya2 |
提出日時 | 2021-06-04 22:08:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,071 bytes |
コンパイル時間 | 5,291 ms |
コンパイル使用メモリ | 273,772 KB |
実行使用メモリ | 279,148 KB |
最終ジャッジ日時 | 2024-04-30 03:05:43 |
合計ジャッジ時間 | 71,658 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 535 ms
34,344 KB |
testcase_02 | AC | 34 ms
5,584 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 34 ms
5,584 KB |
testcase_08 | AC | 121 ms
11,856 KB |
testcase_09 | AC | 129 ms
11,516 KB |
testcase_10 | AC | 578 ms
36,304 KB |
testcase_11 | AC | 379 ms
25,292 KB |
testcase_12 | AC | 2,085 ms
100,948 KB |
testcase_13 | AC | 564 ms
33,744 KB |
testcase_14 | AC | 3,856 ms
167,224 KB |
testcase_15 | AC | 34 ms
5,584 KB |
testcase_16 | AC | 775 ms
43,472 KB |
testcase_17 | AC | 353 ms
23,500 KB |
testcase_18 | AC | 185 ms
14,196 KB |
testcase_19 | AC | 1,969 ms
95,440 KB |
testcase_20 | AC | 3,866 ms
168,536 KB |
testcase_21 | AC | 1,132 ms
59,472 KB |
testcase_22 | AC | 878 ms
49,232 KB |
testcase_23 | AC | 232 ms
17,232 KB |
testcase_24 | AC | 3,527 ms
154,960 KB |
testcase_25 | AC | 1,708 ms
86,224 KB |
testcase_26 | AC | 165 ms
12,788 KB |
testcase_27 | AC | 1,620 ms
80,464 KB |
testcase_28 | AC | 1,034 ms
58,316 KB |
testcase_29 | AC | 1,223 ms
66,256 KB |
testcase_30 | AC | 2,295 ms
106,708 KB |
testcase_31 | AC | 2,284 ms
106,320 KB |
testcase_32 | AC | 2,660 ms
120,784 KB |
testcase_33 | AC | 2,012 ms
95,696 KB |
testcase_34 | AC | 3,294 ms
144,340 KB |
testcase_35 | AC | 2,594 ms
119,244 KB |
testcase_36 | AC | 3,212 ms
142,932 KB |
testcase_37 | AC | 792 ms
50,384 KB |
testcase_38 | AC | 3,373 ms
150,992 KB |
testcase_39 | AC | 2,948 ms
134,608 KB |
testcase_40 | AC | 3,076 ms
137,424 KB |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | TLE | - |
testcase_45 | TLE | - |
testcase_46 | TLE | - |
testcase_47 | TLE | - |
testcase_48 | TLE | - |
testcase_49 | TLE | - |
testcase_50 | TLE | - |
testcase_51 | TLE | - |
testcase_52 | TLE | - |
testcase_53 | TLE | - |
testcase_54 | TLE | - |
testcase_55 | TLE | - |
testcase_56 | TLE | - |
testcase_57 | TLE | - |
testcase_58 | TLE | - |
testcase_59 | TLE | - |
testcase_60 | TLE | - |
testcase_61 | AC | 2 ms
6,940 KB |
testcase_62 | AC | 2 ms
6,940 KB |
testcase_63 | TLE | - |
ソースコード
#include <bits/stdc++.h> /* #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using bint = mp::cpp_int; */ #include <atcoder/all> #include <iostream> #include <queue> #include <stack> #include <vector> #include <string> #include <set> #include <map> #include <random> #include <bitset> #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) using namespace std; using namespace atcoder; using namespace internal; //alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library' using ll = long long; using ld = long double; using P = pair<int, int>; using PI = pair<pair<int,int>,int>; using PL = pair<long long, long long>; using PLL = pair<pair<long long, long long>, long long>; using Pxy = pair<long double, long double>; const int INF = 1001001007; const int modd = 1000000007; const long long modl = 1000000007LL; const long long mod = 998244353LL; const ll inf = 2e18; template <typename SA> void priv(vector<SA> &ar){ if (ar.size() == 0) cout << endl; else { rep(i,ar.size()-1) cout << ar[i] << " "; cout << ar[ar.size()-1] << endl; } } template <typename SB> void privv(vector<vector<SB>> &ar){ rep(i,ar.size()){ rep(j,ar[i].size()-1) cout << ar[i][j] << " "; cout << ar[i][ar[i].size()-1] << endl; } } template <typename SC> bool range(SC a, SC b, SC x){return (a <= x && x < b);} bool rrange(P a, P b, P xy){ bool s = range(a.first,b.first,xy.first); bool t = range(a.second,b.second,xy.second); return (s && t); } template <typename SD> void sor(vector<SD> &ar){sort(ar.begin(),ar.end());} template <typename SE> void rev(vector<SE> &ar){reverse(ar.begin(),ar.end());} template <typename SF> bool chmin(SF &a, const SF &b){if(a>b){a = b; return true;} return false;} template <typename SG> bool chmax(SG &a, const SG &b){if(a<b){a = b; return true;} return false;} template <typename SH> void eru(vector<SH> &ar){sor(ar);ar.erase(unique(ar.begin(),ar.end()),ar.end());} template <typename SI> SI last(vector<SI> &ar){return ar[ar.size()-1];} template <typename SJ> SJ cel(SJ a, SJ b){if (a % b == 0) return a/b; return a/b +1;} template <typename SK, typename SL> void pout(pair<SK,SL> p) {cout << p.first << " " << p.second << endl;} void yes(){cout << "Yes" << endl;} void no (){cout << "No" << endl;} void yn (bool t){if(t)yes();else no();} void Yes(){cout << "YES" << endl;} void No (){cout << "NO" << endl;} void YN (bool t){if(t)Yes();else No();} void dout() {cout << setprecision(20);} vector<int> dx = {0,1,0,-1}; vector<int> dy = {1,0,-1,0}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; ll gcds(ll a, ll b){ ll c = a % b; while (c != 0){ a = b; b = c; c = a % b; } return b; } int r = 20; ll cnt(vector<ll> &ar, ll x){ ll le = -1; ll ri = ar.size(); ll mid = (le + ri) / 2; while (ri - le > 1){ if (ar[mid] <= x) le = mid; else ri = mid; mid = (le + ri) / 2; } return le + 1; } ll slv(vector<ll> &ar, ll n, ll k, map<PL,ll> &mp){ if (mp.find(PL(n,k)) != mp.end()) return mp[PL(n,k)]; if (n == r) return mp[PL(n,k)] = cnt(ar,k); if (k == 1) return mp[PL(n,k)] = 2; if (n > k) return mp[PL(n,k)] = slv(ar,max(ll(r),k),k,mp); return mp[PL(n,k)] = slv(ar,n-1,k,mp) + slv(ar,n-1,k/n,mp); } int main(){ int n; cin >> n; ll k; cin >> k; ll maxk = 10000000000LL; if (n <= r){ vector<ll> ar; rep(i,1<<n){ ll h = 1; rep(j,n) if (i >> j & 1) h *= j+1; if (h <= maxk) ar.emplace_back(h); } sor(ar); cout << cnt(ar,k) - 1 << endl; } else { vector<ll> ar; rep(i,1<<r){ ll h = 1; rep(j,r) if (i >> j & 1) h *= j+1; if (h <= maxk) ar.emplace_back(h); } sor(ar); map<PL,ll> mp; cout << slv(ar,n,k,mp) - 1 << endl; } }