結果

問題 No.941 商とあまり
ユーザー tko919tko919
提出日時 2019-12-04 15:25:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,338 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 174,236 KB
実行使用メモリ 54,872 KB
最終ジャッジ日時 2024-11-30 15:48:13
合計ジャッジ時間 137,100 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 57 WA * 12 RE * 3 TLE * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//template end

int merge(int a,int b){return a*b+a+b;}
bool ans[500010]={};

int main(){
    int n,x; scanf("%d%d",&n,&x);
    vector<int> a(n);
    rep(i,0,n)scanf("%d",&a[i]);
    if(n==1){
        string s;
        rep(i,1,x+1)if(i==a[0])s+='1'; else s+='0';
        cout<<s<<endl; return 0;
    }
    int base=0;
    rep(i,0,n)base=merge(base,a[i]);
    if(base>x){
        rep(i,0,x)cout<<0; puts(""); return 0;
    }
    ans[base]=1; set<int> val;
    rep(i,0,n)val.insert(a[i]);
    rep(i,0,n)rep(j,i+1,n){
        int add=merge(a[i],a[j]);
        while(add<=x){val.insert(add); add+=a[i];}
        add=merge(a[i],a[j]);
        while(add<=x){val.insert(add); add+=a[j];}
    }
    for(int add:val){
        int idx=base;
        while(idx<=x){ans[idx]=1; idx+=add;}
    }
    string s;
    rep(i,1,x+1)if(ans[i])s+='1'; else s+='0';
    cout<<s<<endl;
    return 0;
}
0