#362814 (C++14) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	yakamoto
提出日時	2019-07-26 22:51:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,453 ms / 3,153 ms
コード長	3,734 bytes
コンパイル時間	1,860 ms
コンパイル使用メモリ	173,052 KB
実行使用メモリ	123,264 KB
最終ジャッジ日時	2024-07-02 08:48:37
合計ジャッジ時間	19,723 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 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	2 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	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	4 ms 5,376 KB
testcase_23	AC	4 ms 5,376 KB
testcase_24	AC	7 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	6 ms 5,376 KB
testcase_27	AC	5 ms 5,376 KB
testcase_28	AC	4 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	4 ms 5,376 KB
testcase_31	AC	6 ms 5,376 KB
testcase_32	AC	69 ms 28,672 KB
testcase_33	AC	97 ms 16,896 KB
testcase_34	AC	184 ms 38,272 KB
testcase_35	AC	120 ms 30,720 KB
testcase_36	AC	57 ms 5,376 KB
testcase_37	AC	67 ms 27,008 KB
testcase_38	AC	50 ms 22,656 KB
testcase_39	AC	319 ms 40,320 KB
testcase_40	AC	112 ms 14,848 KB
testcase_41	AC	125 ms 25,216 KB
testcase_42	AC	153 ms 37,504 KB
testcase_43	AC	218 ms 26,368 KB
testcase_44	AC	219 ms 34,944 KB
testcase_45	AC	149 ms 9,472 KB
testcase_46	AC	316 ms 34,560 KB
testcase_47	AC	91 ms 20,736 KB
testcase_48	AC	136 ms 36,992 KB
testcase_49	AC	117 ms 37,760 KB
testcase_50	AC	55 ms 26,752 KB
testcase_51	AC	302 ms 36,096 KB
testcase_52	AC	165 ms 17,536 KB
testcase_53	AC	75 ms 17,280 KB
testcase_54	AC	167 ms 20,352 KB
testcase_55	AC	47 ms 17,536 KB
testcase_56	AC	42 ms 18,048 KB
testcase_57	AC	79 ms 15,232 KB
testcase_58	AC	131 ms 8,064 KB
testcase_59	AC	34 ms 13,696 KB
testcase_60	AC	113 ms 15,232 KB
testcase_61	AC	43 ms 5,376 KB
testcase_62	AC	121 ms 13,440 KB
testcase_63	AC	86 ms 13,952 KB
testcase_64	AC	29 ms 7,296 KB
testcase_65	AC	84 ms 33,408 KB
testcase_66	AC	67 ms 10,752 KB
testcase_67	AC	124 ms 22,528 KB
testcase_68	AC	112 ms 11,392 KB
testcase_69	AC	67 ms 40,320 KB
testcase_70	AC	38 ms 15,104 KB
testcase_71	AC	47 ms 16,000 KB
testcase_72	AC	78 ms 5,376 KB
testcase_73	AC	63 ms 27,264 KB
testcase_74	AC	150 ms 32,896 KB
testcase_75	AC	79 ms 16,256 KB
testcase_76	AC	108 ms 26,112 KB
testcase_77	AC	116 ms 36,864 KB
testcase_78	AC	158 ms 12,416 KB
testcase_79	AC	158 ms 23,040 KB
testcase_80	AC	151 ms 24,192 KB
testcase_81	AC	93 ms 25,088 KB
testcase_82	AC	545 ms 123,264 KB
testcase_83	AC	718 ms 123,136 KB
testcase_84	AC	910 ms 123,136 KB
testcase_85	AC	738 ms 123,136 KB
testcase_86	AC	502 ms 123,136 KB
testcase_87	AC	542 ms 123,136 KB
testcase_88	AC	545 ms 123,136 KB
testcase_89	AC	540 ms 123,136 KB
testcase_90	AC	538 ms 123,136 KB
testcase_91	AC	544 ms 123,136 KB
testcase_92	AC	1,453 ms 123,136 KB
testcase_93	AC	1,399 ms 123,136 KB

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

ソースコード

raw source code

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#ifndef SOLUTION_COMMON_H

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PI = pair<int, int>;
template<class T> using V = vector<T>;
using VI = V<int>;
#define _1 first
#define _2 second

#ifdef MY_DEBUG
# define DEBUG(x) x
#else
# define DEBUG(x)
#endif

template<class T>
inline void debug(T &A) {
  DEBUG(
      for (const auto &a : A) {
        cerr << a << " ";
      }
      cerr << '\n';
  )
}

template<class T, class Func>
inline void debug_with_format(T &A, Func f) {
  DEBUG(
      for (const auto &a : A) {
        cerr << f(a) << " ";
      }
      cerr << '\n';
  )
}

template<class T>
inline void debug_dim2(T &A) {
  DEBUG(
      for (const auto &as : A) {
        debug(as);
      }
  )
}

template<typename ... Args>
inline void debug(const char *format, Args const &... args) {
  DEBUG(
      fprintf(stderr, format, args ...);
      cerr << '\n';
  )
}

template<typename ... Args>
string format(const string &fmt, Args ... args) {
  size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);
  vector<char> buf(len + 1);
  snprintf(&buf[0], len + 1, fmt.c_str(), args ...);
  return string(&buf[0], &buf[0] + len);
}

template<class T1, class T2>
string fmtP(pair<T1, T2> a) {
  stringstream ss;
  ss << "(" << a._1 << "," << a._2 << ")";
  return ss.str();
}

#define SOLUTION_COMMON_H

#endif //SOLUTION_COMMON_H


class PrimeFactorization {
public:
  VI prime, factor;

  PrimeFactorization(int MAX): factor(MAX + 1) {
    for (int i = 2; i <= MAX; ++i) {
      if (factor[i] == 0) {
        factor[i] = i;
        prime.push_back(i);
      }

      int p = 0;
      while (p < prime.size() && prime[p] * i <= MAX) {
        factor[prime[p] * i] = prime[p];
        if (prime[p] == i) break;
        p++;
      }
    }
  }
};

const int MOD = 1000000007;

class D {
public:
  void solve(std::istream& in, std::ostream& out) {
    int N;
    in >> N;
    VI A(N);
    for (int i = 0; i < N; ++i) {
      in >> A[i];
    }

    int MAX = 2000;
    PrimeFactorization pf(MAX);
    int m = pf.prime.size();

    VI rev(MAX + 1);
    for (int i = 0; i < m; ++i) {
      rev[pf.prime[i]] = i;
    }

    VI zero(N + 1);
    V<VI> dp(m, VI(N + 1));
    for (int i = 0; i < N; ++i) {
      if (A[i] == 0) {
        zero[i + 1]++;
      } else {
        int x = A[i];
        while(x > 1) {
          int p = pf.factor[x];
          dp[rev[p]][i + 1]++;
          x /= p;
        }
      }
    }

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < m; ++j) {
        dp[j][i + 1] += dp[j][i];
      }
      zero[i + 1] += zero[i];
    }

    int Q;
    in >> Q;
    for (int t = 0; t < Q; ++t) {
      int P, L, R;
      in >> P >> L >> R;
      L--;R--;
      bool ok = true;
      if (zero[R + 1] > zero[L]) {
        // 途中に0があるので必ず割り切れる
        ok = true;
      } else {
        VI cnt(m); // 素因数ごとの個数
        while(ok && P > 1) {
          bool all = false;
          for (int i = 0; i < m; ++i) {
            if (P % pf.prime[i] == 0) {
              P /= pf.prime[i];
              cnt[i]++;
              all = true;
              break;
            }
          }
          if (!all) ok = false;
        }
        debug(cnt);
        for (int i = 0; i < m; ++i) {
          int c = dp[i][R + 1] - dp[i][L];
          ok = ok && cnt[i] <= c;
          debug("cnt[i]:%d c:%d", cnt[i], c);
        }
      }
      out << (ok ? "Yes" : "NO") << '\n';
    }
  }
};


int main() {
	D solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

yukicoder

結果

テストケース

ソースコード