oj.uz

Submission #437054

# Submission time Handle Problem Language Result Execution time Memory
437054 2021-06-25T17:18:40 Z PinkRabbit Bit Shift Registers (IOI21_registers) C++17
58 / 100
 1 ms 204 KB 
// testing
// prabowo_min.cpp

// Number of instructions: 2 + 12 * log(n)
//   For n = 100 and k = 100, number of instructions: 86

#include "registers.h"

#include <vector>

const int M = 100;
const int B = 2000;

void construct_instructions(int, int n, int k, int) {
  // Append a with (2^k - 1) until n is power of 2
  std::vector<bool> v(B);
  for (; (n & -n) != n; ++n) {
    for (int i = 0; i < k; ++i) {
      v[n*k + i] = true;
    }
  }
  append_store(1, v); append_or(0, 0, 1);

  for (int len = 1; len < n; len <<= 1) {
    // In this iteration, this will happen:
    //   a[i] := min(a[i], a[i + len]) for all i = 0 (mod 2*len)

    std::vector<bool> evenMask(B);
    for (int i = 0; i < n; ++i) {
      if (i % len != 0) continue;
      if (!(i & len)) {
        for (int j = 0; j < k; ++j) evenMask[i*k + j] = true;
      }
    }

    // Initialize some constants (e.g. k=2, len=2):
    //   EvenReg: 110000001100000011000...
    const int kEvenReg = M - 3, kOddReg = M - 2;
    append_store(kEvenReg, evenMask);

    // Separate a[x] where x/(2^len) is odd/even
    const int kEvenPos = 1, kOddPos = 2;
    append_and(kEvenPos, kEvenReg, 0); append_xor(kOddPos, kEvenPos, 0); append_right(kOddPos, kOddPos, k * len);

    // Create negative of odd positions
    const int kOddNeg = 3;
    append_xor(kOddNeg, kOddPos, kEvenReg);

    // Even - Odd; if a[i] < a[i + len] then the "Add register" at position i*k is 0, otherwise 1
    const int kAddPos = 4;
    append_add(kAddPos, kEvenPos, kOddNeg); append_right(kAddPos, kAddPos, k);

    // Filter the even (then odd) positions that are the "min"
    append_add(kAddPos, kAddPos, kEvenReg); append_and(kEvenPos, kEvenPos, kAddPos);
    append_xor(kAddPos, kAddPos, kEvenReg); append_and(kOddPos, kOddPos, kAddPos);

    append_or(0, kOddPos, kEvenPos);
  }
}

Compilation message

registers.cpp: In function 'void construct_instructions(int, int, int, int)':
registers.cpp:38:33: warning: unused variable 'kOddReg' [-Wunused-variable]
   38 |     const int kEvenReg = M - 3, kOddReg = M - 2;
      |                                 ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Incorrect sorting
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Incorrect sorting
2 Halted 0 ms 0 KB -