제출 #818566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
818566		PixelCat	레지스터 (IOI21_registers)	C++17	47 / 100	1 ms	340 KiB

registers

#include "registers.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

// #define DEBUG
#ifdef DEBUG
#define PRINT(x) append_print(x)
#else
#define PRINT(x)
#endif

/*

function signatures:
  void append_move(int t, int x)
  void append_store(int t, std::vector<bool> v)
  void append_and(int t, int x, int y)
  void append_or(int t, int x, int y)
  void append_xor(int t, int x, int y)
  void append_not(int t, int x)
  void append_left(int t, int x, int p)
  void append_right(int t, int x, int p)
  void append_add(int t, int x, int y)
  void append_print(int t)

registers:
  0  input/output
  1  current min
  2  mask for i-th bit (only first person)
  3  mask for i-th bit (everyone)
  4  -mask
  5  (input & mask)
  6  (input & mask) + (-mask)
  7  fill with 1 iff everyone has one
  8  complement of m[7]
  9  dead ppl

*/

void make_masks(int n, int k, int i) {
    vector<bool> m_one(2000, 0), m_all(2000, 0), m_negall(2000, 1);
    m_one[i] = 1;
    for(int j = i; j < n * k; j += k) {
        m_all[j] = 1;
        m_negall[j] = 0;
    }
    For(j, 0, i - 1) m_negall[j] = 0;
    m_negall[i] = 1;
    append_store(2, m_one);
    append_store(3, m_all);
    append_store(4, m_negall);
}

void construct_instructions(int s, int n, int k, int q) {
    assert(s == 0);

    /*
    
    from highest bit to lowest:
    1. extract i-th bit
    2. everyone is 1?
      -> yes: add to answer
      -> no: kill some ppl
    
    * mask: all i-th bit
    * -mask: (~mask) + 1
    * (input & mask) + (-mask) should be 0 if everyone is 1
    
    */

    Forr(i, k - 1, 0) {
        make_masks(n, k, i);  // = 3 operations

        // extract all ppl
        append_and(5, 0, 3);
        append_add(6, 4, 5);
        append_right(8, 6, 1000);
        append_not(7, 8);  // = 7 operations

        // update answer
        append_and(2, 2, 7);
        append_or(1, 1, 2);  // = 9 operations

        if(!i) break;

        // kill bad guys
        append_and(5, 5, 8);
        append_or(9, 5, 9);
        append_right(9, 9, 1);
        append_or(0, 0, 9);
        // For(j, 0, i - 1) {
        //     append_right(9, 5, 1);
        //     append_or(5, 9, 5);
        // }
        // append_and(5, 5, 8);
        // append_or(0, 0, 5);

        PRINT(0);
        PRINT(1);
    }
    append_move(0, 1);
}

/*

0 2 1 1000
0 0
0 1
1 0
1 1
-1

move 1 0
right 1 1 1
and 0 0 1
0
0
0
1


1 2 1 1000
0 0
0 1
1 0
1 1
-1

move 1 0
right 1 1 1
and 2 0 1
or 3 0 1
left 3 3 1
or 0 2 3
0 0
0 1
0 1
1 1

*/

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