結果
| 問題 | No.2334 Distinct Cards |
| ユーザー |
 ma2yuki
|
| 提出日時 | 2023-06-02 22:44:42 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 60 ms / 2,000 ms |
| コード長 | 33,348 bytes |
| コンパイル時間 | 4,601 ms |
| コンパイル使用メモリ | 230,936 KB |
| 実行使用メモリ | 9,644 KB |
| 最終ジャッジ日時 | 2024-06-09 00:29:21 |
| 合計ジャッジ時間 | 5,957 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 3 ms
5,376 KB |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 3 ms
5,376 KB |
| testcase_12 | AC | 49 ms
7,400 KB |
| testcase_13 | AC | 50 ms
7,424 KB |
| testcase_14 | AC | 50 ms
7,396 KB |
| testcase_15 | AC | 51 ms
7,424 KB |
| testcase_16 | AC | 51 ms
7,408 KB |
| testcase_17 | AC | 60 ms
9,640 KB |
| testcase_18 | AC | 60 ms
9,640 KB |
| testcase_19 | AC | 60 ms
9,644 KB |
| testcase_20 | AC | 14 ms
5,376 KB |
| testcase_21 | AC | 13 ms
5,376 KB |
| testcase_22 | AC | 13 ms
5,376 KB |
| testcase_23 | AC | 2 ms
5,376 KB |
ソースコード
/*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
/*
template
ref1:https://github.com/tatyam-prime/kyopro_library
ref2: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;
#endif
using 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;
else
ng = 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());
}
#endif
template <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<<endl
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
print(head);
putchar(' ');
out(tail...);
return 0;
}
#ifdef DEBUG
inline 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<<endl
template <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<<endl
template <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を確認
}