結果

問題 No.941 商とあまり
ユーザー sigma425sigma425
提出日時 2019-12-04 01:06:09
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,906 bytes
コンパイル時間 2,350 ms
コンパイル使用メモリ 211,140 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 03:19:41
合計ジャッジ時間 8,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 4 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 30 ms
5,248 KB
testcase_14 AC 5 ms
5,248 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 30 ms
5,248 KB
testcase_18 AC 19 ms
5,248 KB
testcase_19 AC 13 ms
5,248 KB
testcase_20 AC 3 ms
5,248 KB
testcase_21 AC 3 ms
5,248 KB
testcase_22 AC 4 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 5 ms
5,248 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 6 ms
5,248 KB
testcase_32 WA -
testcase_33 AC 3 ms
5,248 KB
testcase_34 AC 18 ms
5,248 KB
testcase_35 AC 18 ms
5,248 KB
testcase_36 AC 5 ms
5,248 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 3 ms
5,248 KB
testcase_40 AC 4 ms
5,248 KB
testcase_41 AC 3 ms
5,248 KB
testcase_42 AC 4 ms
5,248 KB
testcase_43 AC 4 ms
5,248 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 AC 4 ms
5,248 KB
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 AC 4 ms
5,248 KB
testcase_58 AC 7 ms
5,248 KB
testcase_59 AC 5 ms
5,248 KB
testcase_60 AC 5 ms
5,248 KB
testcase_61 WA -
testcase_62 AC 8 ms
5,248 KB
testcase_63 AC 6 ms
5,248 KB
testcase_64 AC 5 ms
5,248 KB
testcase_65 AC 8 ms
5,248 KB
testcase_66 WA -
testcase_67 AC 10 ms
5,248 KB
testcase_68 WA -
testcase_69 AC 12 ms
5,248 KB
testcase_70 AC 18 ms
5,248 KB
testcase_71 WA -
testcase_72 WA -
testcase_73 AC 18 ms
5,248 KB
testcase_74 AC 25 ms
5,248 KB
testcase_75 AC 12 ms
5,248 KB
testcase_76 AC 16 ms
5,248 KB
testcase_77 AC 16 ms
5,248 KB
testcase_78 AC 22 ms
5,248 KB
testcase_79 AC 34 ms
5,248 KB
testcase_80 AC 30 ms
5,248 KB
testcase_81 AC 32 ms
5,248 KB
testcase_82 AC 31 ms
5,248 KB
testcase_83 AC 22 ms
5,248 KB
testcase_84 AC 22 ms
5,248 KB
testcase_85 AC 37 ms
5,248 KB
testcase_86 AC 14 ms
5,248 KB
testcase_87 AC 26 ms
5,248 KB
testcase_88 AC 34 ms
5,248 KB
testcase_89 AC 47 ms
5,248 KB
testcase_90 AC 46 ms
5,248 KB
testcase_91 AC 37 ms
5,248 KB
testcase_92 AC 41 ms
5,248 KB
testcase_93 AC 37 ms
5,248 KB
testcase_94 AC 6 ms
5,248 KB
testcase_95 AC 53 ms
5,248 KB
testcase_96 AC 47 ms
5,248 KB
testcase_97 AC 44 ms
5,248 KB
testcase_98 AC 3 ms
5,248 KB
testcase_99 AC 5 ms
5,248 KB
testcase_100 AC 32 ms
5,248 KB
testcase_101 AC 4 ms
5,248 KB
testcase_102 AC 3 ms
5,248 KB
testcase_103 AC 26 ms
5,248 KB
testcase_104 AC 3 ms
5,248 KB
testcase_105 AC 3 ms
5,248 KB
testcase_106 AC 2 ms
5,248 KB
testcase_107 AC 2 ms
5,248 KB
testcase_108 WA -
testcase_109 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N,X; cin >> N >> X;
	ll MN = 1;
	V<int> a(N); rep(i,N) cin >> a[i];
	const ll inf = 1e10;
	V<bool> res(X+1);
	auto ANSWER = [&](V<bool> res){
		string s(X,'0');
		rep(i,X) if(res[i+1]) s[i] = '1';
		cout << s << endl;
		exit(0);
	};
	{
		ll A = 1;
		rep(i,N){
			A *= a[i] + 1;
			chmin(A,inf);
		}
		A--;
		if(A > X){
			ANSWER(res);
		}
		MN = A;
	}
	res[MN] = true;
	if(N == 1) ANSWER(res);
	V<int> vx;
	rep(b,1<<N){
		int v = 1;
		rep(i,N) if((b>>i)&1) v *= a[i]+1;
		vx.pb(v);
	}
	sort(all(vx));vx.erase(unique(all(vx)),vx.end());
	for(int x: vx){
		int y = (MN+1)/x;
		if(x>y) break;
		if(x == 1) continue;
		x--,y--;
		show(x);show(y);
		int g = __gcd(x,y);
		rep1(i,y/g+1){
			bool ibreak = false;
			rep1(j,x/g+1){
				int v = x*y+x*i+y*j;
				if(v > X){
					if(j == 1) ibreak = true;
					break;
				}
				res[v] = true;
			}
			if(ibreak) break;
		}
		for(int i=x*y+x+y+x*y;i<=X;i+=g) res[i] = true;
	}
	ANSWER(res);
}
0