Submission #1283209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283209		abc123	레지스터 (IOI21_registers)	C++20	0 / 100	1 ms	344 KiB

registers

#include <bits/stdc++.h>
using namespace std;

void append_move(int t, int y);
void append_store(int t, 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 construct_instructions(int s, int n, int k, int q) {
    // s: 0 = find minimum, 1 = sort
    // n: number of integers
    // k: bits per integer
    // q: max instructions
    // b: total bits (2000) - implicitly used
    
    if (s == 0) {
        // TASK: Find minimum of n numbers
        
        if (n == 2 && k == 1) {
            // Base case: bitwise AND for 1-bit numbers
            append_and(0, 0, 1);
            return;
        }
        
        // For n > 2 or k > 1: extract and compare iteratively
        for (int i = 1; i < n; i++) {
            // Extract i-th number into register 1
            append_move(1, 0);
            append_right(1, 1, i * k);
            
            // Extract current min (in reg 0) into register 2
            append_move(2, 0);
            
            // Compute min(reg2, reg1) and store in reg0
            // Use XOR to find which is smaller
            append_xor(3, 2, 1);      // diff = a XOR b
            
            // For proper min, we'd need multi-bit comparison
            // But for simplicity in subtask 1:
            append_and(0, 2, 1);      // AND gives min for 1-bit
        }
        
    } else {
        // TASK: Sort n numbers in nondecreasing order
        
        if (n == 2 && k == 1) {
            // Bubble sort for 2 1-bit numbers
            // c0 = min, c1 = max
            append_move(1, 0);
            append_right(1, 1, 1);    // Extract 2nd number
            append_and(2, 0, 1);      // min in reg 2
            append_or(3, 0, 1);       // max in reg 3
            append_left(3, 3, 1);     // Shift max left by k
            append_or(0, 2, 3);       // Combine: min in [0:k), max in [k:2k)
            return;
        }
        
        // General sorting for larger inputs
        // Bubble sort using bitwise comparison
        for (int pass = 0; pass < n - 1 && pass < q; pass++) {
            for (int i = 0; i < n - 1 - pass && i + pass + 1 < q; i++) {
                int reg_x = 10 + i;
                int reg_y = 11 + i;
                int temp = 20 + i;
                
                // Extract i-th and (i+1)-th numbers
                append_move(reg_x, 0);
                append_right(reg_x, reg_x, i * k);
                
                append_move(reg_y, 0);
                append_right(reg_y, reg_y, (i + 1) * k);
                
                // Compare and swap if needed using AND/OR
                append_and(temp, reg_x, reg_y);       // min in temp
                append_or(temp + 1, reg_x, reg_y);    // max in temp+1
                
                // Put min at position i, max at position i+1
                // Reconstruct into register 0
                append_left(temp, temp, i * k);
                append_left(temp + 1, temp + 1, (i + 1) * k);
                append_or(0, temp, temp + 1);
            }
        }
    }
}

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