I have been trying to solve AND from classical problem set:http://www.spoj.com/problems/AND/
But I am repeatedly getting wrong answer.I am using the property of 'bitwise and' that 'bitwise and' of a and b is less than or equal to smaller of two.So I created a reference array 'ands' such that ands[i] is a[i]&a[i+1]&.....a[n-1]. where 'a' is the input array sorted in increasing order.Such that if '&' of selected elements (curr) and ands[i] is greater than current ans then return since it won't lead to any decrease in ans.
[bbone=text,727]#include
include
include
include
include
include
include
include
include
define mod 1000000007
using namespace std;
typedef unsigned long long ll;
typedef long double ld;
vector a;
ll n,k,ans,ands[100];
inline ll Scan_f()
{
ll noRead=0;
//register char p=getchar_unlocked();
register char p=getc(stdin);
//for(;p<48 || p>57;p=getchar_unlocked());
for(;p<48 || p>57;p=getc(stdin));
//while(p>47 && p<58){ noRead = (noRead << 3) + (noRead << 1) + (p - '0');p=getchar_unlocked();}
while(p>47 && p<58){ noRead = (noRead << 3) + (noRead << 1) + (p - '0');p=getc(stdin);}
return noRead;
};
void solve(int idx,int cont,ll curr)
{
ll tp;
ans = min(ans,curr);
if(idx == n || cont == k)
return;
tp = curr&ands[idx];
if(tp >= ans)
return;
tp = curr&a[idx];
solve(idx+1,cont+1,tp);
solve(idx+1,cont,curr);
}
int main()
{
//freopen("input2.txt","r",stdin);
long int i,j,T;
ll temp,tp;
temp = 1;
for(i=1;i<=63;i++)
{
temp = temp*2;
}
temp = temp-1;
T = Scan_f();
while(T > 0)
{
n = Scan_f();
k = Scan_f();
for(i=0;i {
tp = Scan_f();
a.push_back(tp);
}
sort(a.begin(),a.end());
for(j=0;j {
ands[j] = a[j];
for(i=j;i {
ands[j] = a[i]&ands[j];
}
}
ans = temp;
solve(0,0,temp);
printf("%llu\n",ans);
a.clear();
memset(ands,temp,sizeof(ands));
T--;
}
return 0;
}
[/bbone]