結果
| 問題 | No.941 商とあまり |
| ユーザー |
 yosupot
|
| 提出日時 | 2019-12-04 01:48:02 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,829 bytes |
| コンパイル時間 | 2,732 ms |
| コンパイル使用メモリ | 212,708 KB |
| 実行使用メモリ | 78,464 KB |
| 最終ジャッジ日時 | 2024-05-06 03:26:49 |
| 合計ジャッジ時間 | 9,385 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
| testcase_100 | -- | - |
| testcase_101 | -- | - |
| testcase_102 | -- | - |
| testcase_103 | -- | - |
| testcase_104 | -- | - |
| testcase_105 | -- | - |
| testcase_106 | -- | - |
| testcase_107 | -- | - |
| testcase_108 | -- | - |
| testcase_109 | -- | - |
ソースコード
# 1 "main.cpp"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "main.cpp"
# 1 "/Users/yosupo/Programs/Algorithm/expander/dummy_include/bits/stdc++.h" 1
#include <bits/stdc++.h>
# 5 "main.cpp" 2
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
# 1 "/Users/yosupo/Programs/Algorithm/src/util/fast_io.h" 1
struct Scanner {
FILE* fp = nullptr;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) reread();
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
while (true) {
succ();
size_t sz = 1;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (st != ed) break;
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) {
ref = 10 * ref + (line[st++] - '0');
}
if (neg) ref = -ref;
return true;
}
template <class T> bool read_single(V<T>& ref) {
for (auto& d : ref) {
if (!read_single(d)) return false;
}
return true;
}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE* _fp) : fp(_fp) {}
};
struct Printer {
public:
template <bool F = false> void write() {}
template <bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(' ');
write_single(h);
write<true>(t...);
}
template <class... T> void writeln(const T&... t) {
write(t...);
write_single('\n');
}
Printer(FILE* _fp) : fp(_fp) {}
~Printer() { flush(); }
private:
static constexpr size_t SIZE = 1 << 15;
FILE* fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write_single(const char& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
void write_single(const T& val) {
for (char c : val) write_single(c);
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write_single(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val;
}
size_t len = 0;
while (val) {
small[len++] = char('0' + (val % 10));
val /= 10;
}
reverse(small, small + len);
memcpy(line + pos, small, len);
pos += len;
}
template <class T> void write_single(const V<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
# 15 "main.cpp" 2
# 40 "main.cpp"
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
return os << "P(" << p.first << ", " << p.second << ")";
}
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
os << "[";
for (auto d : v) os << d << ", ";
return os << "]";
}
# 1 "/Users/yosupo/Programs/Algorithm/src/bitop.h" 1
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(ull x) { return __builtin_popcountll(x); }
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }
# 52 "main.cpp" 2
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
V<bool> solve(ll m, V<ll> v) {
int n = int(v.size());
V<bool> ans(m + 1);
if (n == 1) {
ans[v[0]] = true;
return ans;
}
ll mi = 1, md = TEN(9);
for (ll d : v) {
md = min(md, d - 1);
mi *= d;
if (mi > m) break;
}
if (mi > m) {
return ans;
}
if (md == 1) {
for (ll i = mi; i <= m; i++) ans[i] = true;
return ans;
}
if (n == 2) {
for (ll d: v) {
for (ll i = mi; i <= m; i += d - 1) ans[i] = true;
}
return ans;
}
VV<int> dp(1 << n, V<int>(m + 1, 0));
for (int i = 0; i < n; i++) {
dp[1 << i][v[i]] = 1;
}
V<ll> mul(1 << n);
for (int f = 0; f < (1 << n); f++) {
mul[f] = 1;
for (int i = 0; i < n; i++) {
if (f & (1 << i)) mul[f] *= v[i];
}
}
int gc = 10;
for (int f = 1; f < (1 << n); f++) {
if (popcnt(uint(f)) == 1) continue;
ll rem = mi / mul[f];
for (int g = 1; g < f; g++) {
if (~f & g) continue;
int h = f ^ g;
for (ll x = mul[g]; x <= m; x++) {
if (!dp[g][x]) {
continue;
}
gc++;
for (ll y = mul[h]; x * y * rem <= m; y++) {
if (!dp[h][y]) {
continue;
}
for (ll i = x * y; i * rem <= m; i += (x - 1)) {
if (dp[f][i] == gc) break;
dp[f][i] = gc;
}
}
}
}
}
for (ll i = 1; i <= m; i++) {
if (dp[(1 << n) - 1][i]) ans[i] = true;
}
return ans;
}
int main() {
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
int n; ll x;
sc.read(n, x);
V<ll> a(n);
sc.read(a);
for (ll& d: a) d++;
auto ans = solve(x + 1, a);
for (int i = 2; i <= x + 1; i++) {
auto f = ans[i];
pr.write(f ? '1' : '0');
}
pr.writeln();
return 0;
}