fork(1) download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <sstream>
  7. #include <bitset>
  8. #include <string>
  9. #include <regex>
  10. using namespace std;
  11.  
  12. char binaryToHex(string s) {
  13.     if(s == "0000") {
  14.         return '0';
  15.     } else if(s == "0001") {
  16.         return '1';
  17.     } else if(s == "0010") {
  18.         return '2';
  19.     } else if(s == "0011") {
  20.         return '3';
  21.     } else if(s == "0100") {
  22.         return '4';
  23.     } else if(s == "0101") {
  24.         return '5';
  25.     } else if(s == "0110") {
  26.         return '6';
  27.     } else if(s == "0111") {
  28.         return '7';
  29.     } else if(s == "1000") {
  30.         return '8';
  31.     } else if(s == "1001") {
  32.         return '9';
  33.     } else if(s == "1010") {
  34.         return 'A';
  35.     } else if(s == "1011") {
  36.         return 'B';
  37.     } else if(s == "1100") {
  38.         return 'C';
  39.     } else if(s == "1101") {
  40.         return 'D';
  41.     } else if(s == "1110") {
  42.         return 'E';
  43.     } else {
  44.         return 'F';
  45.     }
  46. }
  47.  
  48. const char* hexToBinary(char c) {
  49.     switch(toupper(c)) {
  50.         case '0': return "0000";
  51.         case '1': return "0001";
  52.         case '2': return "0010";
  53.         case '3': return "0011";
  54.         case '4': return "0100";
  55.         case '5': return "0101";
  56.         case '6': return "0110";
  57.         case '7': return "0111";
  58.         case '8': return "1000";
  59.         case '9': return "1001";
  60.         case 'A': return "1010";
  61.         case 'B': return "1011";
  62.         case 'C': return "1100";
  63.         case 'D': return "1101";
  64.         case 'E': return "1110";
  65.         default: return "1111";
  66.     }
  67. }
  68.  
  69. // Removes leading zeroes from answer, or outputs one '0' if s is all zeroes
  70. void outputAnswer(string s) {
  71.     cout<<regex_replace(s, regex("^0+(?!$)"), "")<<"\n";
  72. }
  73.  
  74. int main() {
  75.     int Q;
  76.     cin>>Q;
  77.     while(Q > 0) {
  78.         int k;
  79.         cin>>k;
  80.         string aHex, bHex, cHex;
  81.         cin>>aHex>>bHex>>cHex;
  82.         string A, B, C;
  83.         // Convert aHex, bHex, cHex to binary with the most significant bit first (big endian)
  84.         for(int i = 0; i < aHex.size(); i++) {
  85.             A += hexToBinary(aHex[i]);
  86.         }
  87.         for(int i = 0; i < bHex.size(); i++) {
  88.             B += hexToBinary(bHex[i]);
  89.         }
  90.         for(int i = 0; i < cHex.size(); i++) {
  91.             C += hexToBinary(cHex[i]);
  92.         }
  93.  
  94.         // Make all strings the same size (since they could have a different number of bits)
  95.         int longestString;
  96.         if(A.size() >= B.size() && A.size() >= C.size()) {
  97.             longestString = A.size();
  98.         } else if(B.size() >= A.size() && B.size() >= C.size()) {
  99.             longestString = B.size();
  100.         } else if(C.size() >= A.size() && C.size() >= B.size()) {
  101.             longestString = C.size();
  102.         }
  103.         A = string(longestString-A.size(), '0') + A;
  104.         B = string(longestString-B.size(), '0') + B;
  105.         C = string(longestString-C.size(), '0') + C;
  106.  
  107.         // Step 1: Check if A | B = C is possible in less than K steps
  108.         for(int i = 0; i < A.size(); i++) {
  109.             if(C[i] == '0') {
  110.                 // We require both A[i] and B[i] to be 0
  111.                 if(A[i] != '0') {
  112.                     A[i] = '0';
  113.                     k--;
  114.                 }
  115.                 if(B[i] != '0') {
  116.                     B[i] = '0';
  117.                     k--;
  118.                 }
  119.             } else {
  120.                 // We require at least one of A[i] or B[i] to be 1
  121.                 if(A[i] == '0' && B[i] == '0') {
  122.                     B[i] = '1'; // Since we require a '1' and A to be as small as possible
  123.                     k--;
  124.                 }
  125.             }
  126.         }
  127.         if(k < 0) {
  128.             cout<<"-1\n";
  129.             Q--;
  130.             continue;
  131.         }
  132.         // Step 2: Make A and B as small as possible
  133.         for(int i = 0; i < A.size(); i++) {
  134.             if(k == 0) {
  135.                 break;
  136.             }
  137.             if(C[i] == '1' && A[i] == '1') {
  138.                 if(k > 1 && B[i] == '0') {
  139.                     // Swap to make A smaller
  140.                     A[i] = '0';
  141.                     B[i] = '1';
  142.                     k -= 2;
  143.                 } else if(B[i] == '1') {
  144.                     // Reduce A
  145.                     A[i] = '0';
  146.                     k--;
  147.                 }
  148.             }
  149.         }
  150.         string answerA, answerB;
  151.         for(int i = 0; i < A.size()-3; i+=4) {
  152.             answerA += binaryToHex(A.substr(i, 4));
  153.             answerB += binaryToHex(B.substr(i, 4));
  154.         }
  155.         outputAnswer(answerA);
  156.         outputAnswer(answerB);
  157.         Q--;
  158.     }
  159.     return 0;
  160. }
Success #stdin #stdout 0s 15344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AwjvFd
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!