- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 114 lines of C++ from the credited upstream file abc264_c.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 10 loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <iostream>2#include <map>3#include <vector>4 5using namespace std;6 7int main() {8 unsigned int h1 = 0, w1 = 0;9 cin >> h1 >> w1;10 vector<int> a_row(w1, 0);11 vector<vector<int>> a(h1, a_row);12 for (auto& ar : a) {13 for (auto& ac : ar) {14 cin >> ac;15 }16 }17 18 unsigned int h2 = 0, w2 = 0;19 cin >> h2 >> w2;20 vector<int> b_row(w2, 0);21 vector<vector<int>> b(h2, b_row);22 for (auto& br : b) {23 for (auto& bc : br) {24 cin >> bc;25 }26 }27 28 29 map<unsigned int, bool> deleted_row;30 map<unsigned int, bool> collect_row;31 for (unsigned int ai = 0; ai < h1; ai++) {32 bool collect_a_row = false;33 for (unsigned int bi = 0; bi < h2; bi++) {34 if (collect_row.count(bi) != 0) {35 continue;36 }37 unsigned int bjv_count = 0;38 unsigned int bj = 0;39 unsigned int aj = 0;40 while (true) {41 if (bj == w2 || aj == w1) {42 break;43 }44 45 if (a[ai][aj] == b[bi][bj]) {46 bjv_count++;47 bj++;48 }49 50 aj++;51 }52 if (bjv_count == w2) {53 collect_row[bi] = true;54 collect_a_row = true;55 break;56 }57 }58 if (!collect_a_row) {59 deleted_row[ai] = true;60 }61 }62 63 if (h1 - deleted_row.size() < h2) {64 cout << "No" << endl;65 return 0;66 }67 68 69 map<unsigned int, bool> deleted_column;70 map<unsigned int, bool> collect_column;71 for (unsigned int aj = 0; aj < w1; aj++) {72 bool collect_a_column = false;73 for (unsigned int bj = 0; bj < w2; bj++) {74 if (collect_column.count(bj) != 0) {75 continue;76 }77 unsigned int biv_count = 0;78 unsigned int bi = 0;79 unsigned int ai = 0;80 while (true) {81 if (deleted_row.count(ai) != 0) {82 ai++;83 }84 85 if (bi == h2 || ai == h1) {86 break;87 }88 89 if (a[ai][aj] == b[bi][bj]) {90 biv_count++;91 bi++;92 }93 94 ai++;95 }96 if (biv_count == h2) {97 collect_column[bj] = true;98 collect_a_column = true;99 break;100 }101 }102 if (!collect_a_column) {103 deleted_column[aj] = true;104 }105 }106 107 if (w1 - deleted_column.size() < w2) {108 cout << "No" << endl;109 return 0;110 }111 112 cout << "Yes" << endl;113 return 0;114}