Submission #952160

#TimeUsernameProblemLanguageResultExecution timeMemory
952160kilkuwuVision Program (IOI19_vision)C++17
32 / 100
5 ms1980 KiB
#ifndef LOCAL #include "vision.h" #else #include <vector> void construct_network(int H, int W, int K); int add_and(std::vector<int> Ns); int add_or(std::vector<int> Ns); int add_xor(std::vector<int> Ns); int add_not(int N); #endif #include <bits/stdc++.h> #ifdef LOCAL #include "template\debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif void construct_network(int H, int W, int K) { auto get_id = [&](int i, int j) -> int { return i * W + j; }; std::vector<int> all_cells(H * W); std::iota(all_cells.begin(), all_cells.end(), 0); std::vector<std::vector<int>> rows(H); std::vector<std::vector<int>> cols(W); for (int i = 0; i < H; i++) { rows[i].resize(W); for (int j = 0; j < W; j++) { rows[i][j] = get_id(i, j); } } for (int j = 0; j < W; j++) { cols[j].resize(H); for (int i = 0; i < H; i++) { cols[j][i] = get_id(i, j); } } int zero_index = add_xor(all_cells); dbg(zero_index); if (H * W == 2 && K != 1) { return; } int one_index = add_not(zero_index); dbg(one_index); if (H * W == 2 && K == 1) { return; } constexpr int NUM_BITS = 9; using Number = std::array<int, NUM_BITS>; auto make_number = [&](int i) { dbg(i); Number rep; for (int b = 0; b < NUM_BITS; b++) { if (i >> b & 1) { rep[b] = add_not(zero_index); } else { rep[b] = add_not(one_index); } } return rep; }; std::vector<Number> numbers(512, {-1}); // 512 numbers auto get_number = [&](int i) { if (numbers[i][0] == -1) { numbers[i] = make_number(i); } return numbers[i]; }; auto apply_multiplier = [&](int index, Number num) { Number res; for (int i = 0; i < NUM_BITS; i++) { res[i] = add_and({index, num[i]}); } return res; }; auto add_number = [&](Number a, Number b) { int carry_bit = zero_index; Number c; for (int i = 0; i < NUM_BITS; i++) { int pxor = add_xor({a[i], b[i]}); // xor of two values c[i] = add_xor({pxor, carry_bit}); int pand = add_and({a[i], b[i]}); int cand = add_and({pxor, carry_bit}); carry_bit = add_or({pand, cand}); } return c; }; auto flip_sign = [&](Number a) { Number res; for (int i = 0; i < NUM_BITS; i++) { res[i] = add_not(a[i]); } return add_number(res, get_number(1)); }; auto sub_number = [&](Number a, Number b) { return add_number(a, flip_sign(b)); }; auto get_distance = [&](std::vector<int> cells) { dbg(cells); int sz = cells.size(); auto value_left = get_number(0); int multiplier = one_index; dbg(value_left, multiplier); for (int i = 0; i < sz; i++) { int tot_multiplier = add_and({cells[i], multiplier}); value_left = add_number(value_left, apply_multiplier(tot_multiplier, get_number(i))); int not_cell = add_not(cells[i]); multiplier = add_and({multiplier, not_cell}); } auto value_right = get_number(0); multiplier = one_index; for (int i = sz - 1; i >= 0; i--) { int tot_multiplier = add_and({cells[i], multiplier}); value_right = add_number(value_right, apply_multiplier(tot_multiplier, get_number(i))); int not_cell = add_not(cells[i]); multiplier = add_and({multiplier, not_cell}); } return sub_number(value_right, value_left); }; auto compare_number = [&](Number a, Number b) { std::vector<int> to_or; Number c; for (int i = 0; i < NUM_BITS; i++) { c[i] = add_xor({a[i], b[i]}); to_or.push_back(c[i]); } int res = add_or(to_or); add_not(res); }; std::vector<int> or_rows(H), or_cols(W); for (int i = 0; i < H; i++) { dbg(rows[i]); or_rows[i] = add_or(rows[i]); dbg(or_rows[i]); } for (int j = 0; j < W; j++) { dbg(cols[j]); or_cols[j] = add_or(cols[j]); dbg(or_cols[j]); } auto dx = get_distance(or_rows); auto dy = get_distance(or_cols); auto tot = add_number(dx, dy); compare_number(tot, get_number(K)); } #ifdef LOCAL #include <cstdio> #include <cassert> #include <string> using namespace std; 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; int main() { 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); while (true) { int rowA, colA, rowB, colB; assert(1 == scanf("%d", &rowA)); if (rowA == -1) break; assert(3 == scanf("%d%d%d", &colA, &rowB, &colB)); 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); } 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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...