結果
問題 | No.941 商とあまり |
ユーザー | maroon_kuri |
提出日時 | 2019-12-04 23:26:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,664 bytes |
コンパイル時間 | 1,995 ms |
コンパイル使用メモリ | 179,240 KB |
実行使用メモリ | 17,964 KB |
最終ジャッジ日時 | 2024-12-14 14:34:04 |
合計ジャッジ時間 | 7,916 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
17,380 KB |
testcase_01 | AC | 6 ms
7,852 KB |
testcase_02 | AC | 5 ms
7,168 KB |
testcase_03 | AC | 6 ms
8,216 KB |
testcase_04 | AC | 3 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 3 ms
6,820 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 13 ms
16,040 KB |
testcase_11 | AC | 11 ms
16,100 KB |
testcase_12 | AC | 12 ms
17,436 KB |
testcase_13 | AC | 16 ms
10,628 KB |
testcase_14 | AC | 14 ms
14,644 KB |
testcase_15 | AC | 13 ms
12,164 KB |
testcase_16 | AC | 10 ms
9,852 KB |
testcase_17 | AC | 18 ms
12,620 KB |
testcase_18 | AC | 8 ms
7,092 KB |
testcase_19 | AC | 10 ms
8,368 KB |
testcase_20 | AC | 3 ms
6,816 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,820 KB |
testcase_24 | AC | 2 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | AC | 15 ms
17,132 KB |
testcase_27 | AC | 10 ms
12,036 KB |
testcase_28 | AC | 16 ms
16,360 KB |
testcase_29 | AC | 17 ms
14,336 KB |
testcase_30 | AC | 16 ms
15,176 KB |
testcase_31 | AC | 17 ms
17,100 KB |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
6,820 KB |
testcase_34 | AC | 9 ms
7,528 KB |
testcase_35 | AC | 7 ms
6,820 KB |
testcase_36 | AC | 12 ms
17,076 KB |
testcase_37 | AC | 14 ms
17,072 KB |
testcase_38 | AC | 8 ms
10,480 KB |
testcase_39 | AC | 3 ms
6,820 KB |
testcase_40 | AC | 3 ms
6,816 KB |
testcase_41 | AC | 3 ms
6,816 KB |
testcase_42 | AC | 2 ms
6,820 KB |
testcase_43 | AC | 6 ms
7,712 KB |
testcase_44 | AC | 6 ms
7,452 KB |
testcase_45 | AC | 13 ms
13,452 KB |
testcase_46 | AC | 15 ms
16,576 KB |
testcase_47 | AC | 10 ms
11,428 KB |
testcase_48 | AC | 3 ms
6,816 KB |
testcase_49 | AC | 7 ms
6,988 KB |
testcase_50 | AC | 3 ms
6,816 KB |
testcase_51 | AC | 3 ms
6,816 KB |
testcase_52 | AC | 4 ms
6,820 KB |
testcase_53 | AC | 3 ms
6,816 KB |
testcase_54 | AC | 12 ms
11,372 KB |
testcase_55 | AC | 9 ms
9,700 KB |
testcase_56 | AC | 11 ms
11,436 KB |
testcase_57 | AC | 4 ms
6,820 KB |
testcase_58 | AC | 6 ms
6,824 KB |
testcase_59 | AC | 12 ms
17,756 KB |
testcase_60 | AC | 13 ms
17,632 KB |
testcase_61 | AC | 11 ms
17,520 KB |
testcase_62 | AC | 14 ms
17,652 KB |
testcase_63 | AC | 14 ms
17,664 KB |
testcase_64 | AC | 14 ms
17,572 KB |
testcase_65 | AC | 15 ms
17,632 KB |
testcase_66 | AC | 15 ms
17,592 KB |
testcase_67 | AC | 16 ms
17,844 KB |
testcase_68 | AC | 14 ms
17,504 KB |
testcase_69 | AC | 16 ms
17,632 KB |
testcase_70 | AC | 16 ms
17,512 KB |
testcase_71 | AC | 16 ms
17,944 KB |
testcase_72 | AC | 16 ms
17,936 KB |
testcase_73 | AC | 17 ms
17,964 KB |
testcase_74 | AC | 19 ms
17,560 KB |
testcase_75 | AC | 18 ms
17,632 KB |
testcase_76 | AC | 18 ms
17,836 KB |
testcase_77 | AC | 18 ms
17,744 KB |
testcase_78 | AC | 17 ms
17,728 KB |
testcase_79 | AC | 18 ms
17,512 KB |
testcase_80 | AC | 18 ms
17,408 KB |
testcase_81 | AC | 18 ms
17,840 KB |
testcase_82 | AC | 18 ms
17,300 KB |
testcase_83 | AC | 18 ms
17,636 KB |
testcase_84 | AC | 19 ms
17,300 KB |
testcase_85 | AC | 19 ms
17,128 KB |
testcase_86 | AC | 19 ms
17,600 KB |
testcase_87 | AC | 20 ms
17,300 KB |
testcase_88 | AC | 19 ms
17,608 KB |
testcase_89 | AC | 20 ms
17,168 KB |
testcase_90 | AC | 19 ms
17,048 KB |
testcase_91 | AC | 21 ms
17,352 KB |
testcase_92 | AC | 21 ms
17,112 KB |
testcase_93 | AC | 19 ms
16,592 KB |
testcase_94 | AC | 6 ms
6,816 KB |
testcase_95 | AC | 17 ms
15,196 KB |
testcase_96 | AC | 18 ms
15,792 KB |
testcase_97 | AC | 19 ms
17,044 KB |
testcase_98 | AC | 3 ms
6,824 KB |
testcase_99 | AC | 6 ms
7,448 KB |
testcase_100 | AC | 14 ms
13,092 KB |
testcase_101 | AC | 2 ms
6,820 KB |
testcase_102 | AC | 3 ms
6,816 KB |
testcase_103 | AC | 13 ms
10,744 KB |
testcase_104 | AC | 2 ms
6,820 KB |
testcase_105 | AC | 2 ms
6,820 KB |
testcase_106 | AC | 2 ms
6,820 KB |
testcase_107 | AC | 2 ms
6,816 KB |
testcase_108 | AC | 2 ms
6,816 KB |
testcase_109 | AC | 2 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,"Line:",__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } void print(ll x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<endl; #else cout<<"Yes"<<endl; #endif if(ex)exit(0); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<endl; #else cout<<"No"<<endl; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<endl; #else cout<<"Possible"<<endl; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<endl; #else cout<<"Impossible"<<endl; #endif if(ex)exit(0); } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } int mask(int i){ return (int(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static random_device rd; static mt19937_64 gen(rd()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } const int xmax=500010; const int nmax=20; bool dp[xmax][nmax]; signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int n,x;cin>>n>>x; int base=1; vi a=readvi(n); rep(i,n){ base*=a[i]+1; if(base-1>x){ cout<<string(x,'0')<<endl; return 0; } } base--; int s=x-base+1; vi ok(s); if(n==1){ ok[0]=1; }else{ rep(i,n)dp[0][i]=1; rep(i,s){ rep(j,n)if(dp[i][j]){ ok[i]=1; if(i+a[j]<s)dp[i+a[j]][j]=1; } if(ok[i]){ rep(j,n){ int k=i*(a[j]+1); if(k<s)dp[k][j]=1; } } } vi vs; rng(bit,1,n){ int w=1; rep(i,n)if(bit&1<<i)w*=a[i]+1; w--; vs.pb(w); } mkuni(vs); for(auto v:vs){ for(int i=v;i<s;i+=v) ok[i]=1; } } string ans(base-1,'0'); rep(i,s)ans+='0'+ok[i]; cout<<ans<<endl; }