Created
July 4, 2016 02:47
-
-
Save jianminchen/9e72d35b50dc570a948e6a308d1c2e55 to your computer and use it in GitHub Desktop.
AorB HackerRank - C++ study code #4
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?