Submission #978515

#	Time	Username	Problem	Language	Result	Execution time	Memory
978515		totoro	Vision Program (IOI19_vision)	C++17	100 / 100	12 ms	2008 KiB

vision

// UNSOLVED SUBTASK 1 (10 pts)
// UNSOLVED SUBTASK 2 (11 pts)
// UNSOLVED SUBTASK 3 (11 pts)
// UNSOLVED SUBTASK 4 (15 pts)
// UNSOLVED SUBTASK 5 (12 pts)
// UNSOLVED SUBTASK 6 (08 pts)
// UNSOLVED SUBTASK 7 (14 pts)
// UNSOLVED SUBTASK 8 (19 pts)
// [+-+]----------------------
// TOTAL      0/100 pts

#include "vision.h"

#include <algorithm>
#include <bitset>
#include <iostream>

const int BITS = 8;

int ic = 0;
int HEIGHT = -1;
int WIDTH = -1;
int ZERO = -1;
int ONE = -1;

int pixelAt(int x, int y) {
    return y * WIDTH + x;
}

std::vector<int> pixelRow(int y) {
    std::vector<int> result;
    for (int x = 0; x < WIDTH; ++x) {
        result.push_back(y * WIDTH + x);
    }
    return result;
}

std::vector<int> pixelColumn(int x) {
    std::vector<int> result;
    for (int y = 0; y < HEIGHT; ++y) {
        result.push_back(y * WIDTH + x);
    }
    return result;
}

int resultOfInstruction(int instructionIndex) {
    return instructionIndex + WIDTH * HEIGHT;
}

std::vector<int> vectorRange(int start, int size) {
    std::vector<int> result;
    result.reserve(size);
    for (int i = start; i < start + size; ++i) {
        result.push_back(i);
    }
    return result;
}

std::vector<int> add(const std::vector<std::vector<int>>& numbers, bool inputCarry, bool keepCarry) {
    std::vector<int> output;
    int carry;
    switch (inputCarry) {
    case false:
        carry = ZERO;
        break;
    case true:
        carry = ONE;
        break;
    }

    for (int bit = BITS - 1; bit >= 0; --bit) {
        std::vector<int> theseBits;
        for (int num = 0; num < numbers.size(); ++num) {
            theseBits.push_back(resultOfInstruction(numbers[num][bit]));
        }
        // vinxor
        add_xor(theseBits);  // ic
        // sumxor
        add_xor({resultOfInstruction(ic), carry});  // ic + 1
        output.push_back(ic + 1);
        // carry and vinxor
        add_and({resultOfInstruction(ic), carry});  // ic + 2
        // vinor
        add_or(theseBits);  // ic + 3
        // not vinxor
        add_not(resultOfInstruction(ic));  // ic + 4
        // vinor and not vinxor
        add_and({resultOfInstruction(ic + 3), resultOfInstruction(ic + 4)});  // ic + 5
        // final or for carry
        add_or({resultOfInstruction(ic + 2), resultOfInstruction(ic + 5)});  // ic + 6
        carry = resultOfInstruction(ic + 6);
        ic += 7;
    }

    if (keepCarry) {
        output.push_back(ic - 1);
    }

    std::reverse(output.begin(), output.end());
    return output;
}

void construct_network(int H, int W, int K) {
    if (H * W == 2) {
        if (K == 1) {
            add_or({0});
        } else {
            add_not({0});
        }
        return;
    }

    HEIGHT = H;
    WIDTH = W;
    add_and({0, 1, 2});
    ++ic;
    add_not(H * WIDTH);
    ++ic;
    ZERO = HEIGHT * WIDTH;
    ONE = HEIGHT * WIDTH + 1;
    // Permanent 0 in i[0] and permanent 1 in i[1]

    for (int row = 0; row < HEIGHT; ++row) {
        add_or(pixelRow(row));
        ++ic;
    }
    // i[2..HEIGHT+2] now contains the information for which rows

    for (int col = 0; col < WIDTH; ++col) {
        add_or(pixelColumn(col));
        ++ic;
    }
    // i[HEIGHT+2..HEIGHT+WIDTH+2] now contains the information for which cols

    add_xor({resultOfInstruction(2)});
    ++ic;
    for (int row = 1; row < HEIGHT; ++row) {
        add_xor({resultOfInstruction(2 + row), resultOfInstruction(HEIGHT + WIDTH + 2 + row - 1)});
        ++ic;
    }
    // i[HEIGHT+WIDTH+2..2*HEIGHT+WIDTH+2] now contains the prefix xors for rows
    // in particular, i[2*HEIGHT+WIDTH+1] now contains the parity of rows
    add_not(resultOfInstruction(2 * HEIGHT + WIDTH + 1));  // i[2*HEIGHT+WIDTH+2]
    ++ic;

    add_xor({resultOfInstruction(HEIGHT + 2)});
    ++ic;
    for (int col = 1; col < WIDTH; ++col) {
        add_xor({resultOfInstruction(2 + HEIGHT + col), resultOfInstruction(2 * HEIGHT + WIDTH + 3 + col - 1)});
        ++ic;
    }
    // i[2*HEIGHT+WIDTH+3..2*HEIGHT+2*WIDTH+3] now contains the prefix xors for cols
    // in particular, i[2*HEIGHT+2*WIDTH+2] now contains the parity of cols
    add_not(resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 2));  // i[2*HEIGHT+2*WIDTH+3]
    ++ic;

    for (int row = 0; row < HEIGHT; ++row) {
        std::bitset<BITS> bits = row;
        for (int i = BITS - 1; i >= 0; --i) {
            switch (bits[i]) {
            case false:
                add_and({ZERO});
                ++ic;
                break;
            case true:
                add_and({resultOfInstruction(2 + row), resultOfInstruction(2 * HEIGHT + WIDTH + 2)});
                ++ic;
                break;
            }
        }
    }
    // i[2*HEIGHT + 2*WIDTH + 4 .. increment in 8 .. 10*HEIGHT + 2*WIDTH + 4] now contains binary of rows

    for (int col = 0; col < WIDTH; ++col) {
        std::bitset<BITS> bits = col;
        for (int i = BITS - 1; i >= 0; --i) {
            switch (bits[i]) {
            case false:
                add_and({ZERO});
                ++ic;
                break;
            case true:
                add_and({ONE, resultOfInstruction(HEIGHT + 2 + col), resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 3)});
                ++ic;
                break;
            }
        }
    }
    // i[10*HEIGHT + 2*WIDTH + 4 .. increment in 8 .. 10*HEIGHT + 10*WIDTH + 4] now contains binary of cols

    for (int row = 0; row < HEIGHT; ++row) {
        add_and({resultOfInstruction(2 + row), resultOfInstruction(HEIGHT + WIDTH + 2 + row)});
        ++ic;
    }
    // i[10*HEIGHT + 10*WIDTH + 4 .. 11*HEIGHT + 10*WIDTH + 4] now contains exactly which row to flip

    for (int col = 0; col < WIDTH; ++col) {
        add_and({resultOfInstruction(HEIGHT + 2 + col), resultOfInstruction(2 * HEIGHT + WIDTH + 3 + col)});
        ++ic;
    }
    // i[11*HEIGHT + 10*WIDTH + 4 .. 11*HEIGHT + 11*WIDTH + 4] now contains exactly which col to flip

    for (int row = 0; row < HEIGHT; ++row) {
        int flippingBit = resultOfInstruction(10 * HEIGHT + 10 * WIDTH + 4 + row);
        for (int bit = 0; bit < BITS; ++bit) {
            add_xor({resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 4 + row * BITS + bit), flippingBit});
            ++ic;
        }
    }
    // i[11*HEIGHT + 11*WIDTH + 4 .. increment in 8 .. 19*HEIGHT + 11*WIDTH + 4] now contains binary row with one flipped

    for (int col = 0; col < WIDTH; ++col) {
        int flippingBit = resultOfInstruction(11 * HEIGHT + 10 * WIDTH + 4 + col);
        for (int bit = 0; bit < BITS; ++bit) {
            add_xor({resultOfInstruction(10 * HEIGHT + 2 * WIDTH + 4 + col * BITS + bit), flippingBit});
            ++ic;
        }
    }
    // i[19*HEIGHT + 11*WIDTH + 4 .. increment in 8 .. 19*HEIGHT + 19*WIDTH + 4] now contains binary col with one flipped

    std::vector<std::vector<int>> rowsInBinary;
    for (int row = 0; row < HEIGHT; ++row) {
        std::vector<int> inBinary;
        for (int bit = 0; bit < BITS; ++bit) {
            inBinary.push_back(11 * HEIGHT + 11 * WIDTH + 4 + row * BITS + bit);
        }
        rowsInBinary.push_back(inBinary);
    }
    std::vector<int> rowSum = add(rowsInBinary, true, false);

    std::vector<std::vector<int>> colsInBinary;
    for (int col = 0; col < WIDTH; ++col) {
        std::vector<int> inBinary;
        for (int bit = 0; bit < BITS; ++bit) {
            inBinary.push_back(19 * HEIGHT + 11 * WIDTH + 4 + col * BITS + bit);
        }
        colsInBinary.push_back(inBinary);
    }
    std::vector<int> colSum = add(colsInBinary, true, false);

    std::vector<int> finalSum = add({rowSum, colSum}, false, true);  // 9 bit number

    std::bitset<9> target = K;
    for (int bit = 0; bit < 9; ++bit) {
        switch (target[bit]) {
        case false:
            add_not(resultOfInstruction(finalSum[9 - 1 - bit]));
            ++ic;
            break;
        case true:
            add_or({resultOfInstruction(finalSum[9 - 1 - bit])});
            ++ic;
            break;
        }
    }

    add_and(vectorRange(resultOfInstruction(ic - 9), 9));
    ++ic;

    return;
}

Compilation message (stderr)

vision.cpp: In function 'std::vector<int> add(const std::vector<std::vector<int> >&, bool, bool)':
vision.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int num = 0; num < numbers.size(); ++num) {
      |                           ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19