fork download
copy 
  1. #include<iostream>
  2. #include <cstdio>
  3.  
  4. #define ARR_SIZE  1564//taking my chunks to be long long ints which are 64 bits.So performance becomes 64 times
  5. #define ZERO_CHAR   '0'
  6. using namespace std;
  7. int main() {
  8.     unsigned long long A[ARR_SIZE], B[ARR_SIZE], C[ARR_SIZE+1],
  9.     value_a = 0, value_b = 0; 
  10.     bool transfer = 0;
  11.  
  12.     int j = 0, k = 0, i = 0, n, q, pos;
  13.     char a[100001], b[100001], cmd[32], bit;
  14.  
  15.     scanf("%d %d\n", &n, &q);
  16.  
  17.     cin.getline(a,100001);
  18.     cin.getline(b,100001);
  19.  
  20.     while (n--) {//converting the binary string into array of shorts
  21.         value_a |= (a[n] - ZERO_CHAR) << k;
  22.         value_b |= (b[n] - ZERO_CHAR) << k;
  23.         k++;
  24.         if (k == 64) {
  25.             A[j] = value_a;
  26.             B[j++] = value_b;
  27.             value_a = value_b = k = 0;
  28.         }
  29.     }
  30.  
  31.     if (k) {
  32.         A[j] = value_a;
  33.         B[j] = value_b;
  34.     }
  35.  
  36.     while(q--) {
  37.         cin.getline(cmd,32);
  38.         if (cmd[4] == 'a') {
  39.             sscanf(cmd, "set_a %d %c", &pos, &bit);//bit is either '0' or '1'No 2 scanfs.just 1 sscanf does the trick.no need to take care of getchar
  40.             j = pos >> 6;//j=pos/16 here j is the chunk A[j] which will be modified
  41.             k = 1 << (pos % 64);//pos%16 gives us the bit position within the chunk A[j]
  42.             A[j] = (bit - ZERO_CHAR) ? A[j] | k : A[j] & (~k);//if 1 then set bit else reset bit
  43.         } else if (cmd[4] == 'b') {
  44.             sscanf(cmd, "set_b %d %c", &pos, &bit);
  45.             j = pos >> 6;
  46.             k = 1 << (pos % 64);
  47.             B[j] = (bit - ZERO_CHAR) ? B[j] | k : B[j] & (~k);
  48.         } else {
  49.             sscanf(cmd, "get_c %d", &pos);
  50.             j = pos >> 6;//j is index for the chunk
  51.             k = pos % 64;//the position within the chunk which we want to get
  52.  
  53.             transfer = 0;//carry
  54. 			//the trick is to calculate the sum only till the bit that u want to find in the result
  55.             for (i = 0; i <= j; i++) {
  56.                 C[i] = A[i] + B[i] + transfer;
  57. 				bool carryin=C[i]>>63^A[i]>>63^B[i]>>63;
  58. 				bool check=(A[i]>>63&B[i]>>63|carryin&A[i]>>63|carryin&B[i]>>63);
  59.                 if(check)
  60. 				transfer=1;
  61. 				else
  62. 				transfer=0;
  63. 				//transfer = value >> 16;
  64.             }
  65.  
  66.             printf("%c", C[j] & (1 << k) ? '1' : '0');
  67.         }
  68.     }
  69.  
  70.     return 0;
  71. }
Runtime error #stdin #stdout 0s 2840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lGkUmN
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 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!