Codeforces/B. Lost Permutation.cpp at main · armaanepiic/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//Bismillahir rahmanir rahim
//Arman Hossain C193033
//Programming is nothing but an addiction.
//https://codeforces.com/contest/1759/problem/B
#include <bits/stdc++.h>
using namespace std;


using ll    =   long long int;
using ull   =   unsigned long long;
using vi    =   vector < int >;
using vll   =   vector < ll >;
using vc    =   vector < char >;
using vs    =   vector < string >;
using vvi   =   vector < vector < int > >;
using vpi   =   vector < pair < int, int > >;
using vvs   =   vector < vector < string > >;


#define     pb              push_back
#define     mp              make_pair
#define     ff              first
#define     ss              second
#define     sortv           sort(v.begin(), v.end())
#define     rev_sortv       sort(v.begin(), v.end(), greater<int>())
#define     inv             vi v;for(int i = 0; i < n; ++i){int x;cin >> x; v.pb(x);};
#define     out(v)          for(auto value:v){cout<<value<<" ";}cout<<endl;
#define     pout(p)         for(auto value:p){cout<<value.ff<<" "<<value.ss<<endl;}cout<<endl;
#define     sz(s)           (s).length()
#define     all(x)          (x).begin(), (x).end()
#define     digits(x)       trunc(log10(x))+1
#define     maxelement(x)   max_element(v.begin(),v.end()) - v.begin()
#define     minelement(x)   min_element(v.begin(),v.end()) - v.begin()
// string to int stoi(x)
// int/double to string to_string(x)


int dx[8] = {1, -1, 0,  0, 1,  1, -1, -1};
int dy[8] = {0,  0, 1, -1, 1, -1,  1, -1};
string alpha = " abcdefghijklmnopqrstuvwxyz";


int main()
{
#ifndef ONLINE_JUDGE
    freopen("F:input.txt", "r", stdin);
    freopen("F:output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;  cin >> t;
    while (t--) {
        int n , k;
        cin >> n >> k;
        // vector<int>v;
        set<int>s;
        ll count = k;
        for (int i = 0; i < n; ++i)
        {
            int x;
            cin >> x;
            // v.pb(x);
            s.insert(x);
            count += x;
        }
        // sort(all(v));
        int sum = 0;
        if (s.size() != n)
            cout << "NO" << endl;
        else
        {
            bool flag = true;
            for (int i = 1; 1; ++i)
            {
                if (binary_search(s.begin() , s.end() , i)) {
                    continue;
                }
                else
                {
                    sum += i;
                    if(sum > k){
                        flag == false;
                        break;
                    }
                    else if(sum < k)
                        s.insert(i);
                    else if(sum == k){
                        s.insert(i);
                        break;
                    }
                }
            }
            if(!flag)
                cout << "NO" << endl;
            else
            {
                set<int> :: iterator it = s.end();
                --it;
                int temp = *it;
                if(temp*(temp+1)/2 == count)
                    cout << "YES"<< endl;
                else
                    cout << "NO" << endl;
            }
        }
    }


    return 0;
}