Submission #418118

#TimeUsernameProblemLanguageResultExecution timeMemory
418118usachevd0Vision Program (IOI19_vision)C++14
100 / 100
14 ms1656 KiB
#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
#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...