結果
問題 | No.2806 Cornflake Man |
ユーザー | syun0713 |
提出日時 | 2024-07-12 22:03:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 8,425 bytes |
コンパイル時間 | 4,852 ms |
コンパイル使用メモリ | 285,520 KB |
実行使用メモリ | 15,764 KB |
最終ジャッジ日時 | 2024-07-17 20:26:55 |
合計ジャッジ時間 | 6,309 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 85 ms
10,040 KB |
testcase_01 | AC | 118 ms
12,700 KB |
testcase_02 | AC | 20 ms
6,940 KB |
testcase_03 | AC | 119 ms
12,916 KB |
testcase_04 | AC | 18 ms
6,940 KB |
testcase_05 | AC | 25 ms
6,940 KB |
testcase_06 | AC | 52 ms
7,296 KB |
testcase_07 | AC | 145 ms
14,332 KB |
testcase_08 | AC | 47 ms
7,040 KB |
testcase_09 | AC | 69 ms
9,216 KB |
testcase_10 | AC | 37 ms
6,940 KB |
testcase_11 | AC | 6 ms
6,940 KB |
testcase_12 | AC | 49 ms
7,040 KB |
testcase_13 | AC | 97 ms
10,948 KB |
testcase_14 | AC | 21 ms
6,940 KB |
testcase_15 | AC | 178 ms
15,764 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,944 KB |
コンパイルメッセージ
main.cpp:75:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 75 | void ain(set<T>& Y, auto n) { | ^~~~ main.cpp:82:26: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 82 | void ain(multiset<T>& Y, auto n) { | ^~~~
ソースコード
/*#pragma GCC target("arch=skylake-avx512") #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops")*/ #include<bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; using namespace std; istream& operator>>(istream& is, mint& a) { long long v; is >> v; a = v; return is; } ostream& operator<<(ostream& os, mint& a) { return os << a.val(); } #endif using namespace std; template<typename T> using vec = vector<T>; using ll = long long; using ull = unsigned long long; using vi = vec<int>; using vs = vec<string>; using si = set<int>; using sll = set<ll>; using vc = vec<char>; using vvi = vec<vi>; using vll = vec<ll>; using vvll = vec<vll>; using vsi = vec<si>; using vsll = vec<sll>; using vd = vec<double>; using vvd = vec<vd>; using pii = pair<int, int>; using pll = pair<ll, ll>; using mii = map<int, int>; using mll = map<ll, ll>; using msi = map<string, int>; using vpii = vec<pii>; using vpll = vec<pll>; using spii = set<pii>; using spll = set<pll>; using vb = vector<bool>; using vvb = vector<vb>; #define rep(i,j,n) for(ll i=j;i<n;i++) #define rrep(i,j,n) for (ll i = n-1; i >=j; i--) #define rp(i,n) rep(i,0,n) #define rrp(i,n) rrep(i,0,n) #define all(v) v.begin(), v.end() #define pb push_back #define ins insert #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define yn(jg) cout<<(jg? "Yes":"No")<<endl; #define NL {cout<<endl;} #define n0 {cout<<"-1"<<endl;} #define lwb lower_bound #define upb upper_bound #define sz size() #define fi first #define se second #define nxp next_permutation ll mod0 = 998244353, lmax = 2e18, inf = 1050000000; double pi = 3.141592653589793238462643; vll vh = { 998244353, 998244853, 1000000007, 1000000009, 1012924417 }; template<typename... T> void in(T&... X) { (cin >> ... >> X); } template<typename T> void ain(vec<T>& Y) { rp(K, Y.size()) cin >> Y[K]; } template<typename T> void ain(set<T>& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template<typename T> void ain(multiset<T>& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template<typename T> void ain(pair<T, T> &a) { cin >> a.fi >> a.se; } template<typename T> void bin(vec<T>& Z) { rp(L, Z.size()) ain(Z[L]); } template<typename T> void aout(T& a) { for (auto I : a) cout << I << " "; cout << endl; } template<typename T> void aout(pair<T,T> a) { cout << a.fi << " " << a.se << endl; } template<typename T> void aout(queue<T> a) { while (!a.empty()) { cout << a.front(); a.pop(); } } template<typename T> void aout(stack<T> a) { while (!a.empty()) { cout << a.top(); a.pop(); } } #define bout(a) {for(auto J:a) aout(J);} template<typename T> bool chmin(T& M1, T M2) { if (M1 > M2) { M1 = M2; return 1; } else return 0; } template<typename T> bool chmax(T& M1, T M2) { if (M1 < M2) { M1 = M2; return 1; } else return 0; } template<typename T> auto vmax(T& a) { return *max_element(all(a)); } template<typename T> auto vmin(T& a) { return *min_element(all(a)); } template<typename T> auto vmaxi(T& a) { return max_element(all(a)) - a.begin(); } template<typename T> auto vmini(T& a) { return min_element(all(a)) - a.begin(); } vector<pair<char, ll>> rle(string rr) { vector<pair<char, ll>> ret; char lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector<pair<int, ll>> rle(vi rr) { vector<pair<int, ll>> ret; int lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector<pair<ll, ll>> rle(vll rr) { vector<pair<ll, ll>> ret; ll lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } template<typename T> auto lwa(vector<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端) auto i = lwb(all(a), b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwa(set<T>& a, T b) {//aでbより小さい最大の値のイテレータ auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwa(multiset<T>& a, T b) {//aでbより小さい最大の値のイテレータ auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(vector<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端) auto i = lwb(all(a), b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(set<T>& a, T b) {//aでb以下の最大の値のイテレータ auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(multiset<T>& a, T b) {//aでb以下の最大の値のイテレータ auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> vec<T> rsw(vec<T>& a) {//累積和 vec<T> b = a; rep(i, 1, b.size()) b[i] += b[i - 1]; return b; } bool kai(string S) {//回文か判定 bool ans = 1; rp(i, S.size()) if (S[i] != S[S.size() - 1 - i]) ans = 0; return ans; } sll yk(ll n) {//約数全列挙O(sqrt(N)),set<int> sll yaku; for (ll i = 1; i * i <= n; i++) if (n % i == 0) { yaku.insert(i); yaku.insert(n / i); } return yaku; } vi ssa(int n) {//n:必要な素数の最大値 素数全列挙 vector<int> prime; vector<int>lpf(n + 1, 0); rep(i, 2, n + 1) { if (lpf[i] == 0) { lpf[i] = i; prime.push_back(i); } for (int k : prime) { if (k * i > n || k > lpf[i]) break;//k最小素因数よりk<=i lpf[k * i] = k;//kを最小素因数に持つ数k*iを拾う } } return prime; } vector<pll> sib(ll x) {//素因数分解 if (x == 1) return vector<pll>(1, { 1,1 }); vector<pll> ans; for (ll i = 2; i * i <= x; i++) {//rootx回iを回しxで割る ll kaisu = 0; while (x % i == 0) { x /= i; kaisu++; } if (kaisu > 0) ans.pb({ i,kaisu }); } if (x != 1) ans.pb({ x,1 }); return ans; } template<typename T> vec<T> zat(vec<T> a) {//座標圧縮 auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); vec<T> c(a.size()); rp(i, a.size()) { c[i] = lwb(all(b), a[i]) - b.begin(); } return c; } template<typename T> void cp(map < T, ll >& a, T b, ll c) {//countplus if (a.find(b) == a.end()) a[b] = c; else a[b] += c; if (a[b] == 0) a.erase(b); } template<typename T> vec<T> inv(vec<T> a) {//0-indexed 逆関数(1-indexedは全要素--) vec<T> ans(a.sz); rp(i, a.sz) { ans[a[i]] = i; } return ans; } vll hs(string s) {//hash vll r = { 0,0,0,0,0 }; rp(i, 5) { rp(j, s.sz) { r[i] *= 27; r[i] += (s[j] - 'a' + 1); r[i] %= vh[i]; } } return r; } vll hsp(ll n) {//hashpow vll r = { 1,1,1,1,1 }; rp(i, 5) { rp(j, n) { r[i] *= 27; r[i] %= vh[i]; } } return r; } template<typename T> bool cross(T a, T b, T c, T d) {//区間(a,b)と区間(c,d)が重なるか判定 return !(b <= c || d <= a); } template<typename T> bool crosse(T a, T b, T c, T d) {//区間[a,b]と区間[c,d]が重なるか判定 return !(b < c || d < a); } //lazy_segtree<S, op, e, F, mapping, composition, id> seg(n); //S:中身型 op:左右合成 e:初期値 //F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない) /* using S = int; using F = int; S op(S a,S b) { return a+b; } S e() { return 0; } S mapping(F x, S a) {//xをaに作用(x初期値に注意) if (x != 0)return x; else return a; } F composition(F f, F g) {//fの方が後(f初期値に注意) if (f != 0)return f; else return g; } F id() {return 0;}*/ //cout<<setprecision(15)<<fixed<< //function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) int main() { int n, m; cin >>n >> m; vi a(n), ans; si b; ain(a); b.insert(0); sort(all(a)); rep(i,1, n) { auto it = b.lwb( a[i]); if (it == b.end() || *it != a[i]) { ans.pb(a[i]); for (int bb = a[i]; bb <= m && b.sz<=n; bb+=a[i]) { b.insert(bb); } } } vi bb; //aout(b); for (auto i : b) bb.pb(i); if (bb != a) cout << -1; else { cout << ans.sz << endl; aout(ans); } }