For the testcase:
1
1 23
178669091
The setter and tester’s solution are giving output as:
178782207
While my correct solution (that is marked as WA during running contest) provides output:
178669091
Basically, the wrong solutions are taking the bits into result that are not set in any of the number provided in input, so instead of breaking out the loop, the wrong solutions are proceeding until K becomes zero.
You can have a look at the solutions and find the difference.
Link to my submission during running contest that is marked as WA:
https://www.codechef.com/viewsolution/34803550
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll tx; cin>>tx; while(tx--)
typedef long long int ll;
int main() {
FIO;
ll power[31];
ll i;
power[0]=1;
for(i=1;i<=30;i++){
power[i]=2*power[i-1];
}
test{
ll n,k,x,i,j;
cin>>n>>k;
ll a[n];
for(i=0;i<n;i++){
cin>>a[i];
}
ll count[31];
for(i=0;i<31;i++){
count[i]=0;
}
for(i=0;i<n;i++){
x=a[i];
j=0;
while(x!=0){
if(x%2==1){
count[j]++;
}
x/=2;
j++;
}
}
vector<pair<ll,ll>>res;
x=1;
for(i=0;i<=30;i++){
res.push_back(make_pair(count[i]*x,50-i));
x*=2;
}
sort(res.begin(),res.end());
ll ans=0;
for(i=30;i>30-k;i--){
ans+=power[50-res[i].second];
}
cout<<ans<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";
void chemthan() {
int test; cin >> test;
assert(1 <= test && test <= 1e3);
while (test--) {
int n, k; cin >> n >> k;
assert(1 <= n && n <= 1e5);
assert(1 <= k && k <= 30);
vi a(n);
vi f(30);
FOR(i, 0, n) {
cin >> a[i];
assert(1 <= a[i] && a[i] <= 1e9);
FOR(j, 0, 30) {
f[j] += bit(a[i], j);
}
}
vector<pair<long long, int>> vals;
FOR(j, 0, 30) {
vals.pb({f[j] * (1LL << j), -j});
}
sort(all(vals)), reverse(all(vals));
vals.resize(k);
int res = 0;
FOR(i, 0, k) res |= 1 << -vals[i].se;
cout << res << "\n";
}
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
My Solution
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define MOD 1000000007
using namespace std;
bool comp(pair<ll, ll> a, pair<ll, ll> b) {
if (a.second == b.second)
return a.first < b.first;
return a.second > b.second;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
FAST
int t;
cin >> t;
while (t--) {
ll n, k, temp;
cin >> n >> k;
ll arr[33];
memset(arr, 0, sizeof(arr));
for (ll i = 0; i < n; i++) {
cin >> temp;
ll j = 0;
while (temp) {
arr[j++] += temp % 2;
temp /= 2;
}
}
vector < pair<ll, ll> > vec;
for (ll i = 0; i < 33; i++) {
vec.push_back(make_pair(i, arr[i] * (ll)pow(2, i)));
}
sort(vec.begin(), vec.end(), comp);
ll res = 0;
// for (ll i = 0; i < 33; i++) {
// cout << vec[i].second << " " << vec[i].first << endl;
// }
for (ll i = 0; i < 33 && k; i++) {
if (vec[i].second) {
res += (ll)pow(2, vec[i].first);
k--;
} else
break;
}
cout << res << endl;
}
}