제출 #798921

#제출 시각아이디문제언어결과실행 시간메모리
798921esomerVision Program (IOI19_vision)C++17
35 / 100
36 ms5060 KiB
#include<bits/stdc++.h> #include "vision.h" using namespace std; // #define endl "\n" typedef long long ll; int h, w; void calc(int n, vector<int>& dist, int k, bool type){ vector<int> val(n); //Whether each row has at least one black. for(int i = 0; i < n; i++){ vector<int> nws; if(type == 0){ for(int j = 0; j < w; j++){ nws.push_back(i * w + j); } }else{ for(int j = 0; j < h; j++){ nws.push_back(j * w + i); } } val[i] = add_or(nws); } vector<int> previous((int)dist.size()); dist[0] = add_xor(val); // cout << "type"<< type << endl; for(int q = 2; q < n; q++){ bool prime = 1; for(int k = 2; k * k <= q; k++){ if((q % k) == 0){ prime = 0; } } if(prime){ vector<int> powers = {q}; int x = q * q; while(x < n){ powers.push_back(x); x *= q; } vector<int> before = {dist[0]}; for(int l = (int)powers.size() - 1; l >= 0; l--){ int d = powers[l]; vector<int> all_res; int will_do = 0; for(int i = 0; i < d && i + d < n; i++){ will_do += 2; } if(will_do > n - d){ for(int i = 0; i + d < n; i++){ all_res.push_back(add_and({val[i], val[i+d]})); } }else{ for(int i = 0; i < d && i + d < n; i++){ vector<bool> done(n, 0); int lefts = n; for(int j = i; j < n; j += d){ done[j] = 1; lefts--; } vector<int> nws; for(int j = 0; j < n; j++){ if(!done[j]) nws.push_back(val[j]); } all_res.push_back(add_not(add_or(nws))); // cout << "d "<< d << " i " << i << " lst " << all_res.back() << endl; } } int orr = add_or(all_res); int orr_before = add_or(before); int nott = add_not(orr_before); previous[d] = add_and({orr, nott}); before.push_back(previous[d]); } } } vector<int> before; for(int d = (int)dist.size() - 1; d > 0; d--){ if(d == 1){ int xorr = add_xor(val); if((int)before.size() == 0){ dist[d] = add_not(xorr); continue; } int orr_before = add_or(before); //It's only 1 if it is not any of the previous. int nott = add_not(orr_before); dist[d] = add_and({nott, add_not(xorr)}); before.push_back(dist[d]); continue; } vector<int> all_res; int x = d; for(int k = 2; k * k <= x; k++){ ll crr = 1; while(x % k == 0){ crr *= k; x /= k; } if(crr != 1){ all_res.push_back(previous[crr]); } } if(x > 1){ all_res.push_back(previous[x]); } int orr = add_and(all_res); if((int)before.size() == 0){ before.push_back(orr); dist[d] = orr; continue; } int orr_before = add_or(before); //Now, I'm one if and(orr, not(orr_before)) is 1, so I'm one and no one before is one). int nott = add_not(orr_before); dist[d] = add_and({orr, nott}); before.push_back(dist[d]); } } void construct_network(int H, int W, int K){ //Now, I want to get the value of each row. h = H; w = W; vector<int> distr(H, 0); vector<int> distc(W, 0); calc(H, distr, K, 0); calc(W, distc, K, 1); vector<int> possibilities; for(int i = 0; i < (int)distr.size() && i <= K; i++){ int j = K - i; if(j >= (int)distc.size()) continue; possibilities.push_back(add_and({distr[i], distc[j]})); } add_or(possibilities); } // 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){ // cout << "type "<< type << endl; // 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", i); // fprintf(log_file, (i ? " %d" : "%d"), memory_cells[i]); // fprintf(log_file, "\n"); // } // 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); // }
#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...