結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー | tatyam |
提出日時 | 2018-09-15 00:33:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,427 bytes |
コンパイル時間 | 1,893 ms |
コンパイル使用メモリ | 205,180 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-06 15:18:13 |
合計ジャッジ時間 | 2,660 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | WA | - |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | WA | - |
ソースコード
#include "bits/stdc++.h" using namespace std; using namespace std::chrono; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pll; #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _overload2(_1,_2,name,...) name #define _re(n) _rep(i,n) #define _rep(i,n) _repi(i,0,n) #define _repi(i,a,b) for(ll i=a;i<b;++i) #define _repc(i,a,b,c) for(ll i=a;i<b;i+=c) #define rep(...) _overload4(__VA_ARGS__,_repc,_repi,_rep,_re)(__VA_ARGS__) #define _rre(n) _rrep(i,n) #define _rrep(i,n) _rrepi(i,0,n) #define _rrepi(i,a,b) for(ll i=b-1;i>=a;i--) #define _rrepc(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrepc,_rrepi,_rrep,_rre)(__VA_ARGS__) #define rbr(i,a) for(auto&& i:a) #define sum(...) accumulate(range(__VA_ARGS__),0) #define _range(i) (i).begin(),(i).end() #define _rangek(i,k) (i).begin(),(i).begin()+k #define range(...) _overload2(__VA_ARGS__,_rangek,_range)(__VA_ARGS__) #define LINF 0x3999999999999999LL #define MOD ll(1000000007) #define MODD ll(998244353) #define INF 0x39999999 #define Yes(i) out(i?"Yes":"No") #define YES(i) out(i?"YES":"NO") #define elif else if //#define START auto start=system_clock::now() //#define END auto end=system_clock::now();cerr<<duration_cast<milliseconds>(end-start).count()<<" ms\n" #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define vec(type,name,size) vector<type> name(size); #define VEC(type,name,size) vector<type> name(size);in(name) #define v(name,size,value) vector<ll>name(size,value) #define vv(type,name,h,w,value) vector<vector<type>>name(h,vector<type>(w,value)) struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}aaaaaaa; template<typename T> inline constexpr T gcd (T a,T b) {if(a==b)return a;else return gcd(b,(a-1)%b+1);} inline void in() {} template<typename T> istream& operator >> (istream& is, vector<T>& vec); template<typename T,size_t size> istream& operator >> (istream& is, array<T,size>& vec); template<typename T,typename L> istream& operator >> (istream& is, pair<T,L>& p); template<typename T> ostream& operator << (ostream& os, vector<T>& vec); template<typename T,typename L> ostream& operator << (ostream& os, pair<T,L>& p); template<typename T> istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;} template<typename T,typename L> istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;} template<typename T> ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;} template<typename T,typename L> ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;} template <class Head, class... Tail> inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);} template <typename T> inline void out(T t){cout<<t<<'\n';} inline void out(){cout<<'\n';} template <class Head, class... Tail> inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);} ll bigMul(ll a, ll b, ll m){ int base = (int)1e9; ll a_low = a % base, a_high = a / base, b_low = b % base, b_high = b / base, result; result = (a_high * b_high) % m; rep(i, 0, 9) result = (result * 10) % m; result = (result + a_low*b_high + b_low*a_high) % m; rep(i, 0, 9) result = (result * 10) % m; result = (result + a_low*b_low) % m; return result; } //n**p % m ll bigPowMod(ll n, ll p, ll m){ ll ans = 1, ln = n; if(p <= 0) return 1; while(p != 0){ if((p & 1) == 1) ans = bigMul(ans, ln, m); //ans = (ans*ln) % m; //ln = (ln * ln) % m; ln = bigMul(ln, ln, m); p = p >> 1; } return ans; } bool suspect(int a, int s, ll d, ll n) { ll x = bigPowMod(a, d, n); if (x == 1) return true; for (int r = 0; r < s; ++r) { if (x == n - 1) return true; //x = x * x % n; x = bigMul(x, x, n); } return false; } //MillerRabin primality test // {2,7,61,-1} is for n < 4759123141 (= 2^32) // {2,3,5,7,11,13,17,19,23,-1} is for n < 10^16 (at least) int test[] = {2,3,5,7,11,13,17,19,23,-1}; bool MillerRabin(ll n) { if (n <= 1 || (n > 2 && n % 2 == 0)) return false; ll d = n - 1; int s = 0; while (d % 2 == 0){ s++; d /= 2; } for (int i = 0; test[i] < n && test[i] != -1; ++i) if (!suspect(test[i], s, d, n)) return false; return true; } bool is_prime(ll n){ if (n < 2) return false; if (n < 4) return true; if (!(n % 2)) return false; if (!(n % 3)) return false; ll sq = sqrt(n); for(int i = 5 ;i < 32; i += 4 - i % 6 / 2){ if (sq < i) return true;; if (!(n % i)) return false; } if(MillerRabin(n))return true; return false; } bool perm(int at,vector<int> list,ll s,int mn,int mx){ if(at==1){ rep(i,mn,mx+1)if(list[i]){ if(is_prime(s*(i<10?10:100)+i)){ out(s*(i<10?10:100)+i); return 1; } return 0; } return 0; } if(!list[1]&&!list[3]&&!list[7]&&!list[9]&&!list[11]&&!list[13])return 0; rrep(i,mn,mx+1){ if(i-1){ if(list[i]){ list[i]--; if(perm(at-1,list,s*(i<10?10:100)+i,0,9))return 1; list[i]++; } } else rrep(j,0,10){ if(j>3){ if(list[1]){ list[1]--; if(perm(at-1,list,s*10+1,j,j))return 1; list[1]++; } } else{ if(list[10+j]){ list[10+j]--; if(perm(at-1,list,s*100+10+j,0,9))return 1; list[10+j]++; }elif(list[1]){ list[1]--; if(perm(at-1,list,s*10+1,j,j))return 1; list[1]++; } } } } return 0; } int main(){ INT(n); vec(int,a,14); rep(n){ INT(m); a[m]++; } if(!perm(n,a,0,0,9))out(-1); }