結果

問題 No.2748 Strange Clock
ユーザー KudeKude
提出日時 2024-04-21 15:46:38
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,290 bytes
コンパイル時間 3,945 ms
コンパイル使用メモリ 311,252 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-21 15:46:44
合計ジャッジ時間 5,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

vector<pair<VL,int>> a[16];

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  a[15] = {
    {{1,1,1,1,2567836929097726,12839184645488638}, 1594323},
    {{1,1,15407021574586366}, 1594323}
  };
  a[14] = {{{1,1,1283918464548862}, 1594323}};
  a[13] = {
    {{1,1,1,1,17832200896510,89161004482558}, 177147},
    {{1,1,106993205379070}, 177147}
  };
  a[12] = {
    {{1,1,1,1,2105190383614,6810910064638}, 39366},
    {{1,1,8916100448254}, 98415}
  };
  a[11] = {
    {{1,1,1,1,123834728446,619173642238}, 19683},
    {{1,1,743008370686}, 19683}
  };
  a[10] = {
    {{1,1,1,1,16339304446,45578059774}, 4374},
    {{1,1,61917364222}, 10935}
  };
  a[9] = {
    {{1,1,1,1,859963390,4299816958}, 2187},
    {{1,1,5159780350}, 2187}
  };
  a[8] = {
    {{1,1,1,1,80885662,349096030}, 108},
    {{1,1,1,1,182409118,247572574}, 18},
    {{1,1,1,1,194353054,235628638}, 18},
    {{1,1,429981694}, 1899},
  };
  a[7] = {
{{1,1,1,1,1,1,1,1,3250078,5971966,5971966,20637790}, 18},
{{1,1,1,1,5971966,29859838}, 207},
{{1,1,1,1,9222046,26609758}, 18},
{{1,1,35831806}, 207}
  };
  a[6]={{{1,1,1,1,1,1,264094,705022,2016862}, 12},
{{1,1,1,1,264094,2721886}, 6},
{{1,1,1,1,705022,2280958}, 42},
{{1,1,2985982}, 111}};
a[5]={{{1,1,1,1,1,1,1,1,15262,15262,26206,192094}, 6},
{{1,1,1,1,15262,233566}, 6},
{{1,1,1,1,41470,207358}, 15},
{{1,1,248830}, 15}};
a[4]={{{1,1,1,1,5470,15262}, 6},
{{1,1,20734}, 15}};
a[3]={{{1,1,1,1,286,1438}, 3},
{{1,1,1726}, 3}};
a[2]={{{1,1,142}, 3}};
a[1]={{{1,1,10}, 1}};
  int pow3[16];
  pow3[0] = 1;
  rep(i, 15) pow3[i+1] = pow3[i] * 3;
  ll pow6[16];
  pow6[0] = 1;
  rep(i, 15) pow6[i+1] = pow6[i] * 6;
  // for (int i = 2; i <= 15; i++) {
  //   ll tot = a1[i];
  //   for (auto [d, cnt] : a2[i]) tot += cnt * 2;
  //   assert(tot == pow3[i]);
  // }
  int n;
  ll m;
  cin >> n >> m;
  const ll period = (ll)pow3[n] << (2 * n);
  int ans = 0;
  for (auto& [d, cnt] : a[n]) for (auto d : d) if (m < d) ans += cnt;
  cout << ans << endl;
  // if (m >= period) {
  //   cout << 0 << '\n';
  //   return 0;
  // }
  // if (n == 1) {
  //   cout << int(m < 10) << '\n';
  //   return 0;
  // }
  // int ans = a1[n];
  // for (auto [d, cnt] : a2[n]) {
  //   if (d < m) ans += cnt;
  //   if (period - d < m) ans += cnt;
  // }
  // cout << ans << '\n';
  // unordered_map<long long, VL> mp;
  // rep(s, pow3[n]) {
  //   int t = 0;
  //   ll u = 0;
  //   int tmp = s;
  //   rep(i, n) {
  //     int r = tmp % 3;
  //     tmp /= 3;
  //     t += (r << (2 * i));
  //     u += r * pow6[i];
  //   }
  //   static VL r, m;
  //   r = {s, t};
  //   m = {pow3[n], 1 << (2 * n)};
  //   auto [y, z] = crt(r, m);
  //   assert(z == (ll)pow3[n] << (2 * n));
  //   ll offset = (u - y) % pow6[n];
  //   if (offset < 0) offset += pow6[n];
  //   mp[offset].emplace_back(y);
  // }
  // map<VL, int> dup;
  // for (auto& [k, v] : mp) {
  //   // if (v.size() >= 2) {
  //     // assert(v.size() == 2);
  //     // sort(all(v));
  //     // ll x1 = v[0], x2 = v[1];
  //     // ll d = x2 - x1;
  //     // cout << d << ',';
  //   // }
  //   static VL tmp;
  //   tmp.clear();
  //   sort(all(v));
  //   int sz = v.size();
  //   rep(i, sz - 1) tmp.emplace_back(v[i+1] - v[i]);
  //   tmp.emplace_back(period + v[0] - v[sz-1]);
  //   sort(all(tmp));
  //   dup[tmp]++;
  // }
  // cout << '\n';
  // for (auto& [k, v] : dup) {
  //   cout << "{{";
  //   bool first = true;
  //   for (auto t : k) {
  //     if (!first) cout << ',';
  //     cout << t;
  //     first = false;
  //   }
  //   cout << "}, " << v << "},\n";
  // }
}
0