結果
問題 | No.2334 Distinct Cards |
ユーザー |
|
提出日時 | 2023-06-02 22:44:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 33,348 bytes |
コンパイル時間 | 4,679 ms |
コンパイル使用メモリ | 222,188 KB |
最終ジャッジ日時 | 2025-02-13 19:45:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function ‘void scan(int&)’: main.cpp:460:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 460 | void scan(int& a) { scanf("%d", &a); } | ~~~~~^~~~~~~~~~ main.cpp: In function ‘void scan(unsigned int&)’: main.cpp:461:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 461 | void scan(unsigned& a) { scanf("%u", &a); } | ~~~~~^~~~~~~~~~ main.cpp: In function ‘void scan(long int&)’: main.cpp:462:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 462 | void scan(long& a) { scanf("%ld", &a); } | ~~~~~^~~~~~~~~~~ main.cpp: In function ‘void scan(long long int&)’: main.cpp:463:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 463 | void scan(long long& a) { scanf("%lld", &a); } | ~~~~~^~~~~~~~~~~~ main.cpp: In function ‘void scan(long long unsigned int&)’: main.cpp:464:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 464 | void scan(unsigned long long& a) { scanf("%llu", &a); } | ~~~~~^~~~~~~~~~~~ main.cpp: In function ‘void scan(float&)’: main.cpp:470:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 470 | void scan(float& a) { scanf("%f", &a); } | ~~~~~^~~~~~~~~~ main.cpp: In function ‘void scan(double&)’: main.cpp:471:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ��
ソースコード
/*https://twitter.com/noimi_kyopro/status/1599530868158369793?s=20&t=WGdck_EIsxY7Hc7e2sjn8g*/#ifdef ma2#ifdef DEBUG#include "atcoder/my_template_debug.hpp"#else#include "atcoder/my_template.hpp"#endif#else/*templateref1:https://github.com/tatyam-prime/kyopro_libraryref2:https://tatyam.hatenablog.com/entry/2019/12/15/003634*/#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <deque>#include <forward_list>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iostream>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;using uint = unsigned;using pcc = pair<char, char>;using pii = pair<int, int>;using pll = pair<ll, ll>;using pil = std::pair<int, long long>;using pli = std::pair<long long, int>;using pdd = pair<double, double>;using tuplis = array<ll, 3>;template <class T>using pq = priority_queue<T, vector<T>, greater<T>>;const ll LINF = 0x1fffffffffffffff;const ll MINF = 0x7fffffffffff;const ll LPLMT = 10000010; // O(n)のloop上限const ll NLGLMT =200010; // O(NlogN)のloop上限(これで指定されたfor文の中にO(logN)の処理を書く)const ll N2LMT = 3010; // O(n^2)のloop上限const ll N3LMT = 110; // O(n^3)のloop上限const ll N4LMT = 50; // O(n^4)のloop上限const ll TNLMT =20; // O(2^n)のloop上限(実際この計算量になるのは全探索くらいなので,この値自体を使うことはなさそう)(オーダの参考程度に)const int INF = 0x3fffffff;const int MOD = 1000000007;const int MODD = 998244353;const ld DINF = numeric_limits<ld>::infinity();const ld EPS = 1e-9;const ld PI = 3.1415926535897932;const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};#define NXY(nx, ny, x, y, i) \auto [nx, ny] = std::make_pair(x + dx[i], y + dy[i])constexpr char DIR[] = "RDLU";#define overload6(_1, _2, _3, _4, _5, _6, name, ...) name#define overload4(_1, _2, _3, _4, name, ...) name#define overload3(_1, _2, _3, name, ...) name#define overload2(_1, _2, name, ...) name/*繰り返し*/#define rep1(n) for (ll i = 0; i < (n); ++i) // n回repeat#define rep2(i, n) for (ll i = 0; i < (n); ++i) // n回repeat(変数指定)#define rep3(i, a, b) for (ll i = (a); i < (b); ++i) // a-bまでrepeat#define rep4(i, a, b, c) \for (ll i = (a); i < (b); \i += (c)) // a-bまで公差cでrepeat(等差数列で使えそう)#define rep(...) \overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) // repeatまとめ#define rrep1(n) for (ll i = (n); i--;)#define rrep2(i, n) for (ll i = (n); i--;)#define rrep3(i, a, b) for (ll i = (b); i-- > (a);)#define rrep4(i, a, b, c) \for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= (c))#define rrep(...) \overload4(__VA_ARGS__, rrep4, rrep3, rrep2, \rrep1)(__VA_ARGS__) // 逆repeatまとめ#define REP1(n) for (ll i = 1; i <= (n); ++i) // n回repeat#define REP2(i, n) for (ll i = 1; i <= (n); ++i) // n回repeat(変数指定)#define REP3(i, a, b) for (ll i = (a); i <= (b); ++i) // a-bまでrepeat#define REP4(i, a, b, c) \for (ll i = (a); i <= (b); \i += (c)) // a-bまで公差cでrepeat(等差数列で使えそう)#define REP(...) \overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) // repeatまとめ#define RREP1(n) for (ll i = (n); i >= 1; i--)#define RREP2(i, n) for (ll i = (n); i >= 1; i--)#define RREP3(i, a, b) for (ll i = (b); i >= (a); i--)#define RREP4(i, a, b, c) rrep(i, a, b + 1, c)#define RREP(...) \overload4(__VA_ARGS__, RREP4, RREP3, RREP2, \RREP1)(__VA_ARGS__) // 逆repeatまとめ#define each1(i, a) for (auto&& i : a)#define each2(x, y, a) for (auto&& [x, y] : a)#define each3(x, y, z, a) for (auto&& [x, y, z] : a)#define each4(w, x, y, z, a) for (auto&& [w, x, y, z] : a)#define each5(v, w, x, y, z, a) for (auto&& [v, w, x, y, z] : a)#define each(...) \overload6(__VA_ARGS__, each5, each4, each3, each2, \each1)(__VA_ARGS__) // 配列の各要素の読み出し#define all1(i) begin(i), end(i)#define all2(i, a) begin(i), begin(i) + a#define all3(i, a, b) begin(i) + a, begin(i) + b#define all(...) \overload3(__VA_ARGS__, all3, all2, \all1)(__VA_ARGS__) // vectorの始めと終わりの読み取り#define rall1(i) (i).rbegin(), (i).rend()#define rall2(i, k) (i).rbegin(), (i).rbegin() + k#define rall3(i, a, b) (i).rbegin() + a, (i).rbegin() + b#define rall(...) \overload3(__VA_ARGS__, rall3, rall2, rall1)( \__VA_ARGS__) // 逆イテレータの取得(rbegin:末尾,rend:頭)#define MAX1(i, a) (i > a ? i : a)#define MAX2(x, y, a) (x > MAX1(y, a) ? x : MAX1(y, a))#define MAX3(x, y, z, a) (x > MAX2(y, z, a) ? x : MAX2(y, z, a))#define MAX4(w, x, y, z, a) (w > MAX3(x, y, z, a) ? w : MAX3(x, y, z, a))#define MAX5(v, w, x, y, z, a) \(v > MAX4(w, x, y, z, a) ? v : MAX4(w, x, y, z, a))#define MAX(...) \overload6(__VA_ARGS__, MAX5, MAX4, MAX3, MAX2, \MAX1)(__VA_ARGS__) // 配列の各要素の読み出し#define MIN1(i, a) (i < a ? i : a)#define MIN2(x, y, a) (x < MIN1(y, a) ? x : MIN1(y, a))#define MIN3(x, y, z, a) (x < MIN2(y, z, a) ? x : MIN2(y, z, a))#define MIN4(w, x, y, z, a) (w < MIN3(x, y, z, a) ? w : MIN3(x, y, z, a))#define MIN5(v, w, x, y, z, a) \(v < MIN4(w, x, y, z, a) ? v : MIN4(w, x, y, z, a))#define MIN(...) \overload6(__VA_ARGS__, MIN5, MIN4, MIN3, MIN2, \MIN1)(__VA_ARGS__) // 配列の各要素の読み出し#define vsum(...) \accumulate( \all(__VA_ARGS__), \0LL) // vectorの合計(int形で受け付けてしまうので,小数で扱いたい場合はdsumを使う)#define dsum(...) \accumulate(all(__VA_ARGS__), 0.0L) // 小数で扱う(long long doubleなど)#define elif else if#define unless(a) if (!(a))#define mp make_pair#define mt make_tuple/*標準入力*/#define INT(...) \int __VA_ARGS__; \in(__VA_ARGS__) // int型標準入力受付,以下LDまで同様#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 LD(...) \ld __VA_ARGS__; \in(__VA_ARGS__)/*vector操作*/#define SORT(a) sort(all(a)) // 昇順ソート#define RS(a) \sort( \all(a), \greater{}) // sort(vec.begin(), vec.end(), greater<ll>())//降順ソート#define REV(a) reverse(all(a)) // 逆順#define UNIQ(a) sort(all(a)), a.erase(unique(all(a)), end(a))#define LROT(v, x) \std::rotate(v.begin(), v.begin() + x, \v.end()) // 1, 2, ..., n -> 2, ..., n, 1#define RROT(v, x) \std::rotate(v.rbegin(), v.rbegin() + x, \v.rend()) // 1, 2, ..., n -> n, 1, ..., n - 1#define CNCT(a, b) \a.insert(a.end(), all(b)) // vector:aの末尾にvector:bをつなぐ#define FIND(name, val) ((name).find(val) != (name).end())#define ALLPERM(name, func) \{ \std::sort((name).begin(), (name).end()); \do { \func \} while (std::next_permutation((name).begin(), (name).end())); \}#define vec(type, name, ...) \vector<type> name(__VA_ARGS__) // type型vectorの定義#define VEC(type, name, size) \vector<type> name(size); \in(name) // type型vector(size指定)標準入力受付#define vv(type, name, h, ...) \vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define VV(type, name, h, w) \vector<vector<type>> name(h, vector<type>(w)); \in(name)#define IV(type, name, size) \vector<pair<type, int>> name(size); \for (int i = 0; i < size; i++) { \type a_i; \in(a_i); \name[i] = mp(a_i, i); \} // Indexつきvector(pair型Vector,(data,index))#define vvv(type, name, h, w, ...) \vector<vector<vector<type>>> name( \h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))#define vvvv(type, name, a, b, c, ...) \vector<vector<vector<vector<type>>>> name( \a, vector<vector<vector<type>>>( \b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))#define TRYDFS(dfs) \try { \dfs; \} catch (int e) { \return 0; \}template <class T>auto vmin(const T& a) {return *min_element(all(a));}template <class T>auto vmax(const T& a) {return *max_element(all(a));}inline long long popcnt(unsigned long long a) {return __builtin_popcountll(a);}/*https://maspypy.github.io/library/my_template.hpp*/// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)int tbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }int tbit(unsigned x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }int tbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }int tbit(unsigned long long x) {return (x == 0 ? -1 : 63 - __builtin_clzll(x));}// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)int lbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }int lbit(unsigned x) { return (x == 0 ? -1 : __builtin_ctz(x)); }int lbit(long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }int lbit(unsigned long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }bool ispow2(int i) { return i && (i & -i) == i; }ll gcd(ll a, ll b) {while (b) {ll c = b;b = a % b;a = c;}return a;}ll lcm(ll a, ll b) {if (!a || !b) return 0;return a * b / gcd(a, b);}ll intpow(ll a, ll b) {ll ans = 1;while (b) {if (b & 1) ans *= a;a *= a;b /= 2;}return ans;}ll modpow(ll a, ll b, ll p) {if (a >= p) a %= p;ll ans = 1;while (b) {if (b & 1) (ans *= a) %= p;(a *= a) %= p;b /= 2;}return ans;}template <class T, class S>decltype(T() / S()) CEIL(T x, S y) {assert(y != 0);return (y < 0 ? CEIL(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));}template <class T, class S>decltype(T() / S()) FLOOR(T x, S y) {assert(y != 0);return (y < 0 ? FLOOR(-x, -y): (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));}/*ref: https://hitonanode.github.io/cplib-cpp/utilities/rotate90.hpp*/template <typename T>std::vector<std::vector<T>> rot90(const std::vector<std::vector<T>>& in) {const int H = in.size(), W = in[0].size();std::vector<std::vector<T>> ret(W, std::vector<T>(H));for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) ret[j][i] = in[i][W - 1 - j];}return ret;}std::vector<std::string> rot90(const std::vector<std::string>& in) {const int H = in.size(), W = in[0].size();std::vector<std::string> ret(W, std::string(H, '\0'));for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) ret[j][i] = in[i][W - 1 - j];}return ret;}template <typename T>int LIS(std::vector<T>& v) {int res = 0;const T MAX_VALUE =typeid(T) == typeid(int) ? 0x3fffffff : 0x1fffffffffffffff;std::vector<T> mn(v.size() + 1, MAX_VALUE);mn.front() = -MAX_VALUE;for (const T& x : v) {const int id = std::lower_bound(mn.begin(), mn.end(), x) - mn.begin();mn[id] = x;if (res < id) res = id;}return res;}template <class T, class U>bool chmin(T& a, const U& b) {if (a > b) {a = b;return 1;}return 0;}template <class T, class U>bool chmax(T& a, const U& b) {if (a < b) {a = b;return 1;}return 0;}template <class T, class U, class F, class V = decltype(T() + U())>V bins(const T OK, const U NG, const F& judge, const double allowError = 1e-9,int iter = 100) {assert(judge(OK));// assert(not judge(NG));auto islr = [allowError](V ok, V ng) -> bool {if (typeid(V) == typeid(double) or typeid(V) == typeid(long double)) {return std::abs(ok - ng) > allowError;}return std::abs(ok - ng) > 1;};V ok = OK, ng = NG;for (V mid = ng + (ok - ng) / 2; islr(ok, ng) and iter-- > 0;mid = ng + (ok - ng) / 2) {if (judge(mid))ok = mid;elseng = mid;}return ok;}template <typename T>std::vector<std::pair<T, int>> RLE(const std::vector<T>& S) {std::vector<std::pair<T, int>> res;for (const T& c : S) {if (res.empty() or res.back().first != c) {res.emplace_back(c, 1);} else {res.back().second++;}}return res;}std::vector<std::pair<char, int>> RLE(const std::string& S) {std::vector<std::pair<char, int>> res;for (const char& c : S) {if (res.empty() or res.back().first != c) {res.emplace_back(c, 1);} else {res.back().second++;}}return res;}vector<ll> iota(ll n) {vector<ll> a(n);iota(a.begin(), a.end(), 0);return a;} // 0~n-1まで順に入れられたvectorを生成vector<pll> factor(ull x) {vector<pll> ans;for (ull i = 2; i * i <= x; i++)if (x % i == 0) {ans.push_back({i, 1});while ((x /= i) % i == 0) ans.back().second++;}if (x != 1) ans.push_back({x, 1});return ans;} // xの素因数分解{素因数,何個あるか}のvectorを返すmap<ll, ll> factor_map(ull x) {map<ll, ll> ans;for (ull i = 2; i * i <= x; i++)if (x % i == 0) {ans[i] = 1;while ((x /= i) % i == 0) ans[i]++;}if (x != 1) ans[x] = 1;return ans;} // 素因数分解mapVer.キー:素因数,要素=その個数vector<ll> divisor(ull x) {vector<ll> ans;for (ull i = 1; i * i <= x; i++)if (x % i == 0) ans.push_back(i);rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]);return ans;} // 約数が昇順に格納されたvectorを返すtemplate <class T>unordered_map<T, ll> press(vector<T>& a) {auto b = a;sort(all(b));b.erase(unique(all(b)), b.end());unordered_map<T, ll> ans;rep(b.size()) ans[b[i]] = i;// each(i, a) i = ans[i];return ans;} // 圧縮 aの各要素をa内の要素で見た時に昇順で何番目だったかの情報に置き換える,{要素,何番目}を表すunordered_mapを返すtemplate <class T>map<T, ll> press_map(vector<T>& a) {auto b = a;sort(all(b));b.erase(unique(all(b)), b.end());map<T, ll> ans;rep(b.size()) ans[b[i]] = i;// each(i, a) i = ans[i];return ans;} // 圧縮mapVer.int scan() { return getchar(); }void scan(int& a) { scanf("%d", &a); }void scan(unsigned& a) { scanf("%u", &a); }void scan(long& a) { scanf("%ld", &a); }void scan(long long& a) { scanf("%lld", &a); }void scan(unsigned long long& a) { scanf("%llu", &a); }void scan(char& a) {do {a = getchar();} while (a == ' ' || a == '\n');}void scan(float& a) { scanf("%f", &a); }void scan(double& a) { scanf("%lf", &a); }void scan(long double& a) { scanf("%Lf", &a); }void scan(vector<bool>& a) {for (unsigned i = 0; i < a.size(); i++) {int b;scan(b);a[i] = b;}}void scan(char a[]) { scanf("%s", a); }void scan(string& a) { cin >> a; }template <class T>void scan(vector<T>&);template <class T, size_t size>void scan(array<T, size>&);template <class T, class L>void scan(pair<T, L>&);template <class T, size_t size>void scan(T (&)[size]);template <class T>void scan(vector<T>& a) {for (auto&& i : a) scan(i);}template <class T>void scan(deque<T>& a) {for (auto&& i : a) scan(i);}template <class T, size_t size>void scan(array<T, size>& a) {for (auto&& i : a) scan(i);}template <class T, class L>void scan(pair<T, L>& p) {scan(p.first);scan(p.second);}template <class T, size_t size>void scan(T (&a)[size]) {for (auto&& i : a) scan(i);}template <class T>void scan(T& a) {cin >> a;}void in() {}template <class Head, class... Tail>void in(Head& head, Tail&... tail) {scan(head);in(tail...);}void print() { putchar(' '); }void print(bool a) { printf("%d", a); }void print(int a) { printf("%d", a); }void print(unsigned a) { printf("%u", a); }void print(long a) { printf("%ld", a); }void print(long long a) { printf("%lld", a); }void print(unsigned long long a) { printf("%llu", a); }void print(char a) { printf("%c", a); }void print(char a[]) { printf("%s", a); }void print(const char a[]) { printf("%s", a); }void print(float a) { printf("%.15f", a); }void print(double a) { printf("%.15f", a); }void print(long double a) { printf("%.15Lf", a); }void print(const string& a) {for (auto&& i : a) print(i);}#if __has_include(<atcoder/all>)template <int m>void print(const atcoder::static_modint<m>& a) {printf("%d", a.val());}template <int m>void print(const atcoder::dynamic_modint<m>& a) {printf("%d", a.val());}#endiftemplate <class T>void print(const vector<T>&);template <class T, size_t size>void print(const array<T, size>&);template <class T, class L>void print(const pair<T, L>& p);template <class T, size_t size>void print(const T (&)[size]);template <class T>void print(const vector<T>& a) {if (a.empty()) return;print(a[0]);for (auto i = a.begin(); ++i != a.end();) {putchar(' ');print(*i);}}template <class T>void print(const deque<T>& a) {if (a.empty()) return;print(a[0]);for (auto i = a.begin(); ++i != a.end();) {putchar(' ');print(*i);}}template <class T, size_t size>void print(const array<T, size>& a) {print(a[0]);for (auto i = a.begin(); ++i != a.end();) {putchar(' ');print(*i);}}template <class T, class L>void print(const pair<T, L>& p) {print(p.first);putchar(' ');print(p.second);}template <class T, size_t size>void print(const T (&a)[size]) {print(a[0]);for (auto i = a; ++i != end(a);) {putchar(' ');print(*i);}}template <class T>void print(const T& a) {cout << a;}int out() {putchar('\n');return 0;}template <class T>int out(const T& t) {print(t);putchar('\n');return 0;} // cout<<t<<endltemplate <class Head, class... Tail>int out(const Head& head, const Tail&... tail) {print(head);putchar(' ');out(tail...);return 0;}#ifdef DEBUGinline ll __lg(ull __n) {return sizeof(ull) * __CHAR_BIT__ - 1 - __builtin_clzll(__n);}#define debug(...) \{ \print(#__VA_ARGS__); \print(":"); \out(__VA_ARGS__); \}#else#define debug(...) void(0)#endif#define ASK(...) \{ \out('?', __VA_ARGS__); \fflush(stdout); \}#define ANS(...) \{ \out('!', __VA_ARGS__); \fflush(stdout); \}/*判定出力*/int dame() { return out(-1); }int Win(bool i = true) {return out(i ? "Win" : "Lose");} // iがfirstか判断,以下同様int Lose() { return out("Lose"); } // iがfirstか判断,以下同様int Alice(bool i = true) {return out(i ? "Alice" : "Bob");} // iがfirstか判断,以下同様int Bob() { return out("Bob"); } // iがfirstか判断,以下同様int Takahashi(bool i = true) {return out(i ? "Takahashi" : "Aoki");} // iがfirstか判断,以下同様int Aoki() { return out("Aoki"); } // iがfirstか判断,以下同様int first(bool i = true) {return out(i ? "first" : "second");} // iがfirstか判断,以下同様int second() { return out("second"); } // iがfirstか判断,以下同様int First(bool i = true) {return out(i ? "First" : "Second");} // iがfirstか判断,以下同様int Second() { return out("Second"); } // iがfirstか判断,以下同様int yes(bool i = true) { return out(i ? "yes" : "no"); }int no() { return out("no"); }int Yes(bool i = true) { return out(i ? "Yes" : "No"); }int No() { return out("No"); }int YES(bool i = true) { return out(i ? "YES" : "NO"); }int NO() { return out("NO"); }int Yay(bool i = true) { return out(i ? "Yay!" : ":("); }int possible(bool i = true) { return out(i ? "possible" : "impossible"); }int impossible() { return out("impossible"); }int Possible(bool i = true) { return out(i ? "Possible" : "Impossible"); }int Impossible() { return out("Impossible"); }int POSSIBLE(bool i = true) { return out(i ? "POSSIBLE" : "IMPOSSIBLE"); }int IMPOSSIBLE() { return out("IMPOSSIBLE"); }void Case(ll i) { printf("Case #%lld: ", i); }void infprint(int x) { return print(x == INF ? -1 : x); }void infprint(const std::vector<int>& a) {if (a.empty()) return;infprint(a[0]);for (auto i = a.begin(); ++i != a.end();) {putchar(' ');infprint(*i);}}int INFOUT() {putchar('\n');return 0;}template <class T>int INFOUT(const T& t) {infprint(t);putchar('\n');return 0;} // cout<<t<<endltemplate <class Head, class... Tail>int INFOUT(const Head& head, const Tail&... tail) {infprint(head);putchar(' ');INFOUT(tail...);return 0;}void linfprint(long long x) { return print(x == LINF ? -1 : x); }void linfprint(const std::vector<long long>& a) {if (a.empty()) return;linfprint(a[0]);for (auto i = a.begin(); ++i != a.end();) {putchar(' ');linfprint(*i);}}int LINFOUT() {putchar('\n');return 0;}template <class T>int LINFOUT(const T& t) {linfprint(t);putchar('\n');return 0;} // cout<<t<<endltemplate <class Head, class... Tail>int LINFOUT(const Head& head, const Tail&... tail) {linfprint(head);putchar(' ');LINFOUT(tail...);return 0;}template <typename T, typename U, typename V>bool EE(T i, U j, V k) {return i <= j and j <= k;}template <typename T, typename U, typename V>bool CE(T i, U j, V k) {return i < j and j <= k;}template <typename T, typename U, typename V>bool EC(T i, U j, V k) {return i <= j and j < k;}template <typename T, typename U, typename V>bool CC(T i, U j, V k) {return i < j and j < k;}/*vector探索*/template <typename T>T pick_front(std::deque<T>& que) {assert(not que.empty());T x = que.front();que.pop_front();return x;}template <typename T>T pick_back(std::deque<T>& que) {assert(not que.empty());T x = que.back();que.pop_back();return x;}template <typename T>T pick(std::queue<T>& que) {assert(not que.empty());T x = que.front();que.pop();return x;}template <typename T>T pick(std::priority_queue<T>& que) {assert(not que.empty());T x = que.top();que.pop();return x;}template <typename T>T pick(std::priority_queue<T, std::vector<T>, std::greater<T>>& que) {assert(not que.empty());T x = que.top();que.pop();return x;}template <typename T>T pick(std::vector<T>& que) {assert(not que.empty());T x = que.back();que.pop_back();return x;}template <typename T>T pick(std::stack<T>& que) {assert(not que.empty());T x = que.top();que.pop();return x;}#define CNT(v, k) \count(all(v), k) // 配列vの中で要素kが何個あるかを返す(size_t)#define CNTIF(v, l) \count_if( \all(v), \l) // 配列vの中で条件式(lambda式)を満たす個数を返す(ex.int num =// count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});)#define SORT2D(myVec, i) \sort(myVec.begin(), myVec.end(), \[](const vector<ll>& alpha, const vector<ll>& beta) { \return alpha[i] < beta[i]; \}); // i列めでソート/*最大公約数*/template <class T>T vgcd(T m, T n) {return gcd(m, n);}template <class T, class... Args>T vgcd(T a, Args... args) {return vgcd(a, vgcd(args...));}#define vecgcd(a) reduce(all(a), 0LL, gcd<ll, ll>)/*あまり(強制的に正の余りを出力)*/template <class T, class U>void mod(T& n, const U p) {assert(p > 0);if (0 <= n and n < p) return;if (n == p or p == 1) {n = 0;} else if (p == 2) {n &= 1;} else if (abs(n) <= p) {n = p + n;} else {n %= p;if (n < 0) n += p;}}template <class T, class U>T rtmod(T n, const U p) {mod(n, p);return n;}/*逆元 あまりの割り算をするときにこいつをかける(a/b→a*modinv(b))*/// mod. m での a の逆元 a^{-1} を計算するll modinv(ll a, ll m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}u %= m;if (u < 0) u += m;return u;}/*階乗*/ll fac2(ll k, ll a, ll p) {ll sum = 1;for (ll i = k; i > k - a; --i) {sum *= i;sum %= p; // あまりを出力せよ問題の時はこれもやる}return sum;}/*組み合わせnCk*/ll modcomb(ll n, ll k, ll p) {ll c = fac2(n, k, p);c *= modinv(fac2(k, k, p), p);mod(c, p);return c;}/*ダブリング*//*参考:http://satanic0258.hatenablog.com/entry/2017/02/23/222647使える場所:1回遷移した先が明確にわかる時目的:・ある数XのQ乗を求める・根付き木において、ある頂点vのQ個上の親を知る・ある地点からQ回進んだ先を求める*/// int N; // 全体の要素数// int Q;//試行回数ll doubling(const ll N, const ll Q,vector<ll>& a) { // cin>>N>>Q;//標準入力から要素数と試行回数を受け取る場合ll LOG_Q = floor(log2(Q)) + 1;// next[k][i]で、i番目の要素の「2^k個次の要素」を指す// (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、// next[k][i]が指し示す要素番号を-1とします)std::vector<std::vector<ll>> next(LOG_Q + 1, std::vector<ll>(N));// ll a[N];//各要素の次の行き先// next[0]を計算for (int i = 0; i < N; ++i) {next[0][i] = a[i];}// nextを計算for (ll k = 0; k < LOG_Q; ++k) {for (int i = 0; i < N; ++i) {if (next[k][i] == -1) {// 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありませんnext[k + 1][i] = -1;} else {// 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素ですnext[k + 1][i] = next[k][next[k][i]];}}}// ----ここまで準備----// p番目の要素の「Q個次の要素」を求めることを考えますll p = 0;for (ll k = LOG_Q - 1; k >= 0; --k) {if (p == -1) {// pがすでに存在しない要素を指していたら、// それ以降で存在する要素を指すことはないためループを抜けますbreak;}if ((Q >> k) & 1) { // ex(Q=5)5=101(2)であり,2^2+2^0回進むことを表す// Qを二進展開した際、k番目のビットが立っていたら、// pの位置を2^kだけ次にずらしますp = next[k][p];}}return p; // ここでのpが最終的な答えになる}/*素数判定*/bool IsPrime(ll num) {if (num < 2)return false;else if (num == 2)return true;else if (num % 2 == 0)return false; // 偶数はあらかじめ除くdouble sqrtNum = sqrt(num);for (int i = 3; i <= sqrtNum; i += 2) {if (num % i == 0) {// 素数ではないreturn false;}}// 素数であるreturn true;}template <int N>struct nreparray {std::array<int, N> v;nreparray(std::array<int, N> v_) : v(v_) {}struct nrepitr {const std::array<int, N>& v;std::array<int, N> tmp;bool is_end;nrepitr(const std::array<int, N>& v_) : v(v_), tmp(), is_end(false) {}bool operator!=(const nrepitr&) const { return !is_end; }void operator++() {int pos = N - 1;while (pos != -1) {tmp[pos] += 1;if (tmp[pos] == v[pos]) {tmp[pos] = 0;pos -= 1;} else {break;}}if (pos == -1) {is_end = true;}}const std::array<int, N>& operator*() const { return tmp; }};nrepitr begin() const { return nrepitr(v); }nrepitr end() const { return nrepitr(v); }};struct nrepvector {std::vector<int> v;nrepvector(std::vector<int> v_) : v(v_) {}struct nrepitr {const std::vector<int>& v;std::vector<int> tmp;bool is_end;nrepitr(const std::vector<int>& v_): v(v_), tmp(v.size(), 0), is_end(false) {}bool operator!=(const nrepitr&) const { return !is_end; }void operator++() {int pos = v.size() - 1;while (pos != -1) {tmp[pos] += 1;if (tmp[pos] == v[pos]) {tmp[pos] = 0;pos -= 1;} else {break;}}if (pos == -1) {is_end = true;}}const std::vector<int>& operator*() const { return tmp; }};nrepitr begin() const { return nrepitr(v); }nrepitr end() const { return nrepitr(v); }};auto nrep(std::vector<int> v) { return nrepvector(v); }template <class... Ts>auto nrep(Ts... v) {return nreparray<std::tuple_size<std::tuple<Ts...>>::value>({v...});}mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());long long rnd(long long B = 1) {return B == 1 ? rng() : (unsigned long long)rng() % B;}/*ページのソースを表示->command+F->問題文 で問題文コピペする*//*0~n-1までの順列の出力rep(n)v.push_back(i);do{}while(next_permutation(all(v)));*/// ceil()//切り上げ ll(ceil((ld)n/(ld)x))=(n+x-1)/x(整数除算)なのでそっちがいいかも// floor()//切り捨て// round()//四捨五入// deque<ll> deq;//両端キュー使う,先頭と末尾へのアクセスが早い// using std::map;// map<string,ll>memo;//<キー,その要素>,キーの検索が早い,キーは昇順にソートされる#endif/*以下コーディング*/void preprocess();signed solve();void run_testcase();signed main() {preprocess();signed testcase = 1;// scanf("%d", &testcase);//テストケース数を渡すfor (int ti = 1; ti <= testcase; ti++) {// Case(ti);run_testcase();}}void run_testcase() { // 入力と解法を分離させるだけなので,基本的に入力以外何も書かない// Input(面倒なときに分離させる)solve(); // 実装本体はこっちに書く(必要に応じて引数を渡す)}void preprocess() {}signed solve() { // main/*idea:*/// 問題タイトルとサンプル 読め!!!!!!!!!!!!!!!INT(n, k);VEC(int, a, n);map<int, int> memo;each(x, a) memo[x]++;vector<pii> cnt;each(x, y, memo) cnt.emplace_back(y, x);SORT(cnt);int ans = 0;while (k > 0) {k -= pick(cnt).first;ans++;}out(ans);return 0; // checklist.txtを確認}