ahhh my bad !
thank you !
Thanks a lot, it helped 
. I was also facing the same issue.
Thanks for that! It passed. But I do not understand how, with the given constraints, it should matter. If all the elements are the same, even then the value of the map would very well be within the limits of int, which is the size of the array. Any leads? Seems like the test cases were weird.
Any idea why this failed the second task?
https://www.codechef.com/viewsolution/45612811
The main solution is from line 66 to 85.
Your Code, ACfied
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(vector<bool> v) {bool first = true; cerr << "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {cerr << ", ";} first = false; __print(v[i]);} cerr << "}";}
template <size_t N>
void __print(bitset<N> bs) {string res = "<"; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + bs[i]);} res += '>'; cerr << res;}
template<typename T>
void __print(const T &x) {int j = 0; cerr << "{"; for (auto &i: x) cerr << (j++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << "("; __print(x.first); cerr << ", "; __print(x.second); cerr << ")";}
template <typename A, typename B, typename C>
void __print(const tuple<A, B, C> t) {cerr << "("; __print(get<0>(t)); cerr << ", "; __print(get<1>(t)); cerr << ", "; __print(get<2>(t)); cerr << ")";}
template <typename A, typename B, typename C, typename D>
void __print(const tuple<A, B, C, D> t) {cerr << "("; __print(get<0>(t)); cerr << ", "; __print(get<1>(t)); cerr << ", "; __print(get<2>(t)); cerr << ", "; __print(get<3>(t)); cerr << ")";}
void _print() {cerr << " ]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(...) cerr << "~ [ " << #__VA_ARGS__ << " ] => [ "; _print(__VA_ARGS__)
#define debn(...) cerr << "~ [ "; _print(__VA_ARGS__)
#else
#define deb(...)
#define debn(...)
#endif
#define ALL(DS) (DS).begin(), (DS).end()
#define PB push_back
#define EB emplace_back
#define SZ(DS) (int)((DS).size())
#define fo(ITER, LO, UP) for (ITER = (LO); ITER < (UP); ++ITER)
#define foi(ITER, LO, UP) for (int ITER = (LO); ITER < (UP); ++ITER)
#define foll(ITER, LO, UP) for (ITER = (ll)(LO); ITER < (ll)(UP); ++ITER)
#define folli(ITER, LO, UP) for (ll ITER = (ll)(LO); ITER < (ll)(UP); ++ITER)
#define iter(ITER, DS) for (auto &ITER: DS)
const int MOD = 1000000007;
const int INF = 1e9 + 5;
void init() {}
void solve(int testcase) {
ll n, t, r, temp; cin >> n >> t >> r;
map<ll, ll> w;
foi(i, 0, n) {
cin >> temp;
w[temp]++;
}
ll sum = r;
iter(x, w) {
sum += x.first * ((x.second / 2) * 2);
if (sum >= t) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
init();
int T; cin >> T;
for(int t = 1; t <= T; ++t) {
solve(t);
}
}
What are you missing?
map<ll, ll> w;
shall be used instead of
map<int, int> w;
1 Like
But arenāt all the numbers in the int range? I did use lls everywhere elseā¦ Is this some C++ thing or am I just being dumb?
Consider the case when you have to lift at least 10 Units.
Now, the weight you already have is 8 units.
The number of additional weights you can add is 10^5 and all of them are 10^5. In your approach, there is only one element in the map., viz., 10^5. You are adding the product to a variable.
have += i * w[i];
The R.H.S is 10^{10}. It is automatically typecasted to Int which will result in overflow. Hence WA.
2 Likes
Hey bro I used the same logic as yours that finding the pairs of same number but I did it with array like I first sorted it then found out the pairs from start till end, but I didānt understand your working with maps like how did you learn and implement them?
My code:
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
int main() {
// your code goes here
int t;
cin>>t;
while(tā)
{
ll int n, w, wr;
cin>>n>>w>>wr;
ll int a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
sort(a, a+n);
if(wr>=w)
{
cout<<āYES\nā;
continue;
}
//10 10 10 10 10 10
for(int i=0; i<n; i++)
{
if(a[i]==a[i+1]) {
wr+=2*a[i];
i++;
}
}
if(wr>=w) cout<<āYES\nā;
else cout<<āNO\nā;
}
return 0;
}
Thanks a lot.
Better to use long long rather than int.
Iām surprised my solution got accepted. I only considered the even count weights and didnāt add any weights with odd count.
https://www.codechef.com/viewsolution/45583410
1 Like
Canāt the chef place 90 and 10 on the left and 100 on the right?
I had the same problem. Apparently using long long and an if condition before the loop solves it.
Alternatively, decreasing the value of w instead of increasing wr, solves the issue.
this is my solution ā¦ hope helps ā¦ case if odd u can use x-1 thats even weights
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;std::cin >> t;
while(t--){
long long int n,w,wr;std::cin >> n>>w>>wr;
unordered_map<long long int,long long int>weights;
for(long long int i=0 ;i<n;i++){
long long int x;std::cin >> x;weights[x]++;
}
w-=wr;
for(auto it=weights.begin() ; it!=weights.end() ; it++){
if(it->second % 2 == 0){
long long int total = it->first * it->second;
w-=total;
}
else{
long long int total = it->first * (it->second-1);
w-=total;
}
if(w<=0){
break;
}
}
if(w<=0){
std::cout << "YES" << std::endl;
}
else{
cout<<"NO\n";
}
}
return 0;
}