Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 4, 2016 02:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/9e72d35b50dc570a948e6a308d1c2e55 to your computer and use it in GitHub Desktop.
Save jianminchen/9e72d35b50dc570a948e6a308d1c2e55 to your computer and use it in GitHub Desktop.
AorB HackerRank - C++ study code #4
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
const char *digits = "0123456789ABCDEF";
int hexmap[128];
bool getbit(const string &s, int i) {
if(i >= (int)s.size() * 4)
return false;
else
return hexmap[s[i / 4]] >> (i % 4) & 1;
}
string toHex(const vector<bool> &v) {
assert(v.size() % 4 == 0);
string s;
rep(i, v.size() / 4) {
int x = 0;
rep(j, 4)
x |= (v[i * 4 + j] ? 1 : 0) << j;
s += digits[x];
}
while(s.size() > 1 && s.back() == '0')
s.pop_back();
reverse(s.begin(), s.end());
return s;
}
int main() {
rep(i, 16)
hexmap[digits[i]] = i;
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ++ ii) {
int K;
scanf("%d", &K);
string A, B, C;
cin >> A >> B >> C;
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
reverse(C.begin(), C.end());
int n = (int)max({ A.size(), B.size(), C.size() }) * 4;
vector<bool> newA(n), newB(n);
rep(i, n) {
newA[i] = getbit(A, i);
newB[i] = getbit(B, i);
}
int diff = 0;
vector<bool> change(n);
rep(i, n) {
bool a = newA[i], b = newB[i], c = getbit(C, i);
if((a || b) != c) {
if(!c) {
diff += a + b;
newA[i] = newB[i] = false;
} else {
diff += 1;
newB[i] = true;
}
change[i] = true;
}
}
if(diff > K) {
puts("-1");
continue;
}
K -= diff;
for(int i = n - 1; i >= 0; -- i) {
if(getbit(C, i)) {
assert(newA[i] || newB[i]);
if(newA[i] && !newB[i]) {
if(K >= 2) {
newA[i] = false;
newB[i] = true;
K -= 2;
}
} else if(newA[i] && newB[i]) {
if(K >= 1) {
newA[i] = false;
K -= 1;
}
}
}
}
string ansA = toHex(newA), ansB = toHex(newB);
puts(ansA.c_str());
puts(ansB.c_str());
}
return 0;
}
@boddumanohar
Copy link

can you please explain static const int INF = 0x3f3f3f3f why this is used in line 6? Also I've seen people using this in many coding contests. what is this and why is this preferred?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment