oj.uz

Submission #978444

# Submission time Handle Problem Language Result Execution time Memory
978444 2024-05-09T08:28:49 Z totoro Vision Program (IOI19_vision) C++17
0 / 100
 11 ms 1852 KB 
// 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) {
    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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Incorrect 1 ms 424 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Incorrect 1 ms 424 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Incorrect 1 ms 424 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Incorrect 1 ms 424 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 3 ms 780 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Incorrect 0 ms 344 KB WA in grader: Invalid index
22 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 2 ms 732 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 6 ms 1240 KB Output is correct
21 Correct 6 ms 1240 KB Output is correct
22 Correct 6 ms 1240 KB Output is correct
23 Correct 8 ms 1096 KB Output is correct
24 Correct 6 ms 1236 KB Output is correct
25 Correct 6 ms 1236 KB Output is correct
26 Correct 6 ms 1240 KB Output is correct
27 Correct 10 ms 1852 KB Output is correct
28 Correct 10 ms 1800 KB Output is correct
29 Correct 10 ms 1752 KB Output is correct
30 Correct 11 ms 1748 KB Output is correct
31 Correct 10 ms 1752 KB Output is correct
32 Incorrect 0 ms 348 KB WA in grader: Invalid index
33 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1748 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct
8 Correct 6 ms 1268 KB Output is correct
9 Correct 10 ms 1752 KB Output is correct
10 Incorrect 0 ms 344 KB WA in grader: Invalid index
11 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Incorrect 1 ms 424 KB WA in grader: Invalid index
18 Halted 0 ms 0 KB -