Submission #556302

#	Time	Username	Problem	Language	Result	Execution time	Memory
556302		cjoa	Bit Shift Registers (IOI21_registers)	C++17	21 / 100	1 ms	288 KiB

registers

#include "registers.h"

#include <vector>
#include <cstdio>

using namespace std;

const int NBITS = 2000;

enum Register {
   r0  =  0, r1,
   r10 = 10,
   r20 = 20, r21, r22, r23, r24,
   r30 = 30, r31,
   r40 = 40, r41, r42,
   r50 = 50,
   r91 = 91
};

void construct_instructions(int s, int n, int k, int q) {
   if (s == 1)
      return;

   if (n > 2)
      return;

   if (k == 1) {
      append_move(1, 0);      // r[1] := r[0]
      append_right(1, 1, k);  // r[1] := r[1] >> k
      append_and(0, 0, 1);    // r[0] := r[0] & r[1]
      return;
   }

   if (k == 2) {
      vector<bool> V(NBITS, 0);
      V[1] = 1;
      append_store(r91, V);    // r[91] := "10"

      // split array of 2 integers into two registers r0 and r1
      // r1 = r0 >> k
      append_move(r1, r0);
      append_right(r1, r1, k);

      // r10 := r[0] & r[1] & "10"  (r10 has most significante bit of min)
      append_and(r10, r0, r1);
   // append_and(r10, r10, r91);

      // detect whether most significant bit is distinct
      // r[22] := ((r[0] ^ r[1]) & "10")  (distinct)
      // r[23] := r[22] ^ "10"  (equal)
      append_xor(r22, r0, r1);
      append_and(r22, r22, r91);
      append_xor(r23, r22, r91);
      append_print(r22);
      append_print(r23);
      
      // case most significant bit is equal:
      //   contribution of least significant bit is minimum
      // r[30] := r[0] & r[1] & (r23 >> 1)
      append_right(r24, r23, 1);
      //append_and(r30, r0, r1);
      //append_and(r30, r30, r24);
      append_and(r30, r10, r24);

      // case most significant bit is distinct:
      //   carry opposite of most bit significant into least signinicant bit

      // r[40] := (((r[0] ^ "10") & r[22]) >> 1) & r[0]
      append_xor(r40, r0, r91);
      append_and(r40, r40, r22);
      append_right(r40, r40, 1);
      append_and(r40, r40, r0);
      //append_print(r40);

      // r[41] := (((r[1] ^ "10") & r[22]) >> 1) & r[1]
      append_xor(r41, r1, r91);
      append_and(r41, r41, r22);
      append_right(r41, r41, 1);
      append_and(r41, r41, r1);
      //append_print(r41);
      
      append_or(r0, r40, r41);
      append_or(r0, r0, r30);
      append_or(r0, r0, r10);
   }


}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29