Submission #418118

#	Time	Username	Problem	Language	Result	Execution time	Memory
418118		usachevd0	Vision Program (IOI19_vision)	C++14	100 / 100	14 ms	1656 KiB

vision

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "vision.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int add_not(int N);
void construct_network(int n, int m, int k) {
    if (n * m == 2) {
        add_not(add_not(0));
        return;
    }
    int zero = add_and({0, 1, 2});
    int one = add_not(zero);
    
    int last = zero;
    vector<int> px(n);
    for (int i = 0; i < n; ++i) {
        vector<int> a(m);
        for (int j = 0; j < m; ++j)
            a[j] = i * m + j;
        a.push_back(last);
        px[i] = add_xor(a);
        last = px[i];
    }
    last = zero;
    vector<int> py(m);
    for (int j = 0; j < m; ++j) {
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            a[i] = i * m + j;
        a.push_back(last);
        py[j] = add_xor(a);
        last = py[j];
    }
    
    vector<int> D(9);
    for (int b = 0; b < 9; ++b)
        D[b] = zero;
    
    function<void(int)> addD = [&](int c) {
        for (int b = 0; b < 9; ++b) {
            int nx = add_xor({D[b], c});
            int nc = add_and({D[b], c});
            D[b] = nx;
            c = nc;
        }
    };
    
    for (int i = 0; i < n; ++i)
        addD(px[i]);
    for (int j = 0; j < m; ++j)
        addD(py[j]);
    
    vector<int> K(9);
    for (int b = 0; b < 9; ++b)
        K[b] = ((k >> b) & 1 ? one : zero);
    
    vector<int> bxor(9);
    for (int b = 0; b < 9; ++b) {
        bxor[b] = add_xor({D[b], K[b]});
    }
    add_not(add_or(bxor));
}



#ifdef LOCAL
static const int MAX_INSTRUCTIONS = 10000;
static const int MAX_INPUTS = 1000000;

static const int _AND = 0;
static const int _OR = 1;
static const int _XOR = 2;
static const int _NOT = 3;

static inline bool increasing(int a, int b, int c) {
    return a <= b && b <= c;
}

[[noreturn]] static inline void error(string message) {
    printf("%s\n", message.c_str());
    exit(0);
}

class InstructionNetwork {

    struct Instruction {
        int type;
        vector<int> input_indexes;

        inline Instruction(int _type, const vector<int>& _input_indexes):
                type(_type), input_indexes(_input_indexes) {
        }

        inline int apply(int a, int b) const {
            switch (type) {
                case _AND:
                    return a & b;
                case _OR:
                    return a | b;
                case _XOR:
                    return a ^ b;
                default:
                    return 0;
            }
        }

        inline int compute(const vector<int>& memory_cells) const {
            int r = memory_cells[input_indexes[0]];
            if (type == _NOT)
                return 1 - r;
            for (int j = 1; j < (int)input_indexes.size(); j++)
                r = apply(r, memory_cells[input_indexes[j]]);
            return r;
        }
    };

    int input_size;
    int total_inputs;
    vector<Instruction> instructions;

public:

    inline void init(int _input_size) {
        this->input_size = _input_size;
        this->total_inputs = 0;
        this->instructions.clear();
    }

    inline int add_instruction(int type, const vector<int>& input_indexes) {
        if (input_indexes.size() == 0)
            error("Instruction with no inputs");

        if (instructions.size() + 1 > MAX_INSTRUCTIONS)
            error("Too many instructions");

        if (total_inputs + input_indexes.size() > MAX_INPUTS)
            error("Too many inputs");

        instructions.emplace_back(type, input_indexes);
        total_inputs += input_indexes.size();
        int new_index = input_size + (int)instructions.size() - 1;

        for (int input_index : input_indexes)
            if (!increasing(0, input_index, new_index-1))
                error("Invalid index");

        return new_index;
    }

    inline int compute(vector<int> &memory_cells) const {
        for (auto &instruction : instructions)
            memory_cells.push_back(instruction.compute(memory_cells));
        return memory_cells.back();
    }
};


static InstructionNetwork instructionNetwork;

mt19937 rng(1337);

int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    int H, W, K;
    assert(3 == scanf("%d%d%d", &H, &W, &K));

    FILE *log_file = fopen("log.txt","w");

    instructionNetwork.init(H * W);
    construct_network(H, W, K);

    for (int test = 1; ; ++test) {
        int rowA, colA, rowB, colB;
        // assert(1 == scanf("%d", &rowA));
        // if (rowA == -1)
        //     break;
        // assert(3 == scanf("%d%d%d", &colA, &rowB, &colB));
        rowA = rng() % H, colA = rng() % H;
        rowB = rng() % H, colB = rng() % H;
        while (rowA == rowB && colA == colB) {
            rowB = rng() % H, colB = rng() % H;
        }

        if ((!increasing(0, rowA, H-1)) ||
            (!increasing(0, colA, W-1)) ||
            (!increasing(0, rowB, H-1)) ||
            (!increasing(0, colB, W-1)) ||
            (rowA == rowB && colA == colB)) {
            printf("-1\n");
            fprintf(log_file, "-1\n");
            fflush(stdout);
            fflush(log_file);
            continue;
        }

        vector<int> memory_cells;
        for (int row = 0; row < H; row++)
            for (int col = 0; col < W; col++) {
                bool active = (row == rowA && col == colA) || (row == rowB && col == colB);
                memory_cells.push_back(active ? 1 : 0);
            }
        int computation_result = instructionNetwork.compute(memory_cells);

        // printf("%d\n", computation_result);
        // fflush(stdout);

        // for(int i = 0; i < (int)memory_cells.size(); i++)
        //     fprintf(log_file, (i ? " %d" : "%d"), memory_cells[i]);
        // fprintf(log_file, "\n");
        // fflush(log_file);
        
        if (computation_result != (K == labs(rowA - rowB) + labs(colA - colB))) {
            cout << H << ' ' << W << ' ' << K << endl;
            cout << rowA << ' ' << colA << ' ' << rowB << ' ' << colB << endl;
            exit(0);
        }
        
        if (test % 1000 == 0) debug(test);
    }
    fclose(stdin);
}

int add_and(vector<int> Ns) {
    return instructionNetwork.add_instruction(_AND, Ns);
}

int add_or(vector<int> Ns) {
    return instructionNetwork.add_instruction(_OR, Ns);
}

int add_xor(vector<int> Ns) {
    return instructionNetwork.add_instruction(_XOR, Ns);
}

int add_not(int N) {
    vector<int> Ns = {N};
    return instructionNetwork.add_instruction(_NOT, Ns);
}
#endif

• 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