#664159 (C++17) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	narushimas
提出日時	2021-06-06 02:55:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,552 bytes
コンパイル時間	4,563 ms
コンパイル使用メモリ	277,532 KB
実行使用メモリ	14,884 KB
最終ジャッジ日時	2024-11-22 03:49:38
合計ジャッジ時間	132,605 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 12,544 KB
testcase_01	AC	2 ms 10,624 KB
testcase_02	AC	2 ms 10,624 KB
testcase_03	AC	2 ms 12,416 KB
testcase_04	AC	2 ms 10,624 KB
testcase_05	AC	2 ms 12,416 KB
testcase_06	AC	2 ms 10,624 KB
testcase_07	AC	2 ms 12,160 KB
testcase_08	AC	2 ms 10,624 KB
testcase_09	AC	2 ms 12,032 KB
testcase_10	AC	2 ms 10,624 KB
testcase_11	AC	2 ms 12,032 KB
testcase_12	AC	2 ms 10,624 KB
testcase_13	AC	2 ms 12,032 KB
testcase_14	AC	2 ms 10,624 KB
testcase_15	AC	2 ms 12,544 KB
testcase_16	AC	2 ms 10,624 KB
testcase_17	AC	2 ms 12,160 KB
testcase_18	AC	2 ms 10,624 KB
testcase_19	AC	2 ms 12,032 KB
testcase_20	AC	7 ms 10,624 KB
testcase_21	AC	78 ms 12,160 KB
testcase_22	AC	74 ms 12,192 KB
testcase_23	AC	2 ms 10,624 KB
testcase_24	AC	2 ms 12,196 KB
testcase_25	AC	259 ms 10,624 KB
testcase_26	AC	137 ms 10,624 KB
testcase_27	AC	13 ms 12,416 KB
testcase_28	AC	13 ms 10,624 KB
testcase_29	AC	50 ms 12,544 KB
testcase_30	AC	47 ms 10,624 KB
testcase_31	AC	89 ms 12,288 KB
testcase_32	AC	171 ms 10,624 KB
testcase_33	AC	177 ms 12,800 KB
testcase_34	AC	178 ms 10,624 KB
testcase_35	AC	110 ms 12,928 KB
testcase_36	AC	109 ms 12,196 KB
testcase_37	AC	4 ms 10,624 KB
testcase_38	AC	5 ms 12,160 KB
testcase_39	AC	119 ms 10,624 KB
testcase_40	AC	98 ms 10,624 KB
testcase_41	AC	97 ms 12,800 KB
testcase_42	AC	96 ms 12,192 KB
testcase_43	AC	61 ms 10,624 KB
testcase_44	AC	61 ms 10,624 KB
testcase_45	AC	19 ms 12,544 KB
testcase_46	AC	19 ms 10,624 KB
testcase_47	AC	31 ms 12,544 KB
testcase_48	AC	296 ms 12,160 KB
testcase_49	AC	296 ms 10,624 KB
testcase_50	AC	79 ms 10,624 KB
testcase_51	AC	81 ms 12,032 KB
testcase_52	AC	16 ms 10,624 KB
testcase_53	AC	1,164 ms 12,544 KB
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	TLE	-
testcase_57	TLE	-
testcase_58	TLE	-
testcase_59	AC	1,294 ms 5,632 KB
testcase_60	TLE	-
testcase_61	TLE	-
testcase_62	TLE	-
testcase_63	TLE	-
testcase_64	TLE	-
testcase_65	TLE	-
testcase_66	AC	2 ms 5,248 KB
testcase_67	AC	3 ms 5,248 KB
testcase_68	TLE	-
testcase_69	TLE	-
testcase_70	TLE	-
testcase_71	TLE	-
testcase_72	TLE	-
testcase_73	TLE	-
testcase_74	TLE	-
testcase_75	AC	242 ms 5,248 KB
testcase_76	TLE	-
testcase_77	TLE	-
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	TLE	-
testcase_81	TLE	-
testcase_82	AC	10 ms 5,248 KB
testcase_83	TLE	-
testcase_84	TLE	-
testcase_85	TLE	-
testcase_86	TLE	-
testcase_87	TLE	-
testcase_88	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) {}
#endif

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

#define ll long long
#define ld long double
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i, n) for(int i=1; i<=(n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define RFOR(i, a, b) for(int i=(b)-1; i>=(a); --i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define popcnt(x) __builtin_popcountll(x)
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define newline puts("")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<ld>; 
using vs = vector<string>;
using vpii = vector<pii>;
using vpl = vector<pll>; 
using vpd = vector<pdd>;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
using int128 = __int128_t;
using mint = atcoder::modint1000000007;
const ll MOD = 1000000007;
// using mint = atcoder::modint998244353;
// const ll MOD = 998244353;
// using mint = atcoder::modint; //mint::set_mod(mod);

/** debug **/
template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(mint x) { return to_string(x.val()); } 
string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; }
template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; }
template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; }
template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; }
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }

#define endl '\n'
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const long double eps= 1e-10;
const long double PI = 3.141592653589793238462643383279502884L;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

struct EratosSieve {
  int n;
  vector<int> f, primes;
  EratosSieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> _factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<pair<int,int>> factorize(int x) {
    vector<int> fl = _factorList(x);
    if (fl.size() == 0) return {};
    vector<pair<int,int>> res(1, pair<int,int>(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factorize(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};

void solve() {
  int N; cin >> N;
  EratosSieve era(3 * N);
  vi ps;
  rep1(i, N){
    if(era.isPrime(i)) ps.pb(i);
  }
  debug(ps);
  v<map<int, int>> vec(4);
  vec[0][0] = 1;
  
  for(int p : ps){
    rrep(j, 3){
      int nj = j + 1;
      for(auto [k, v] : vec[j]){
        int nk = k + p;
        if(nk >= 3 * N) break;
        vec[nj][nk] += vec[j][k];
      }
    }
  }

  debug(vec);

  ll ans = 0;
  for(auto [k, v] : vec[3]){
    if(era.isPrime(k)) ans += v;
  }
  cout << ans << endl;
}

int main(){
  int tests = 1;
  // scanf("%d", &tests);
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);
  rep1(i, tests){
    solve();
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード