## Editorial for VM 11 Bài 06 - Mã khóa bí mật 3

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int m,n,a[33][33];
vector <int> row[33],col[33];

int invalidRow(int x)
{
vector <int> b;
int cnt=0;
for (int y=1;y<=n+1;y++)
if (a[x][y]) cnt++;
else
if (cnt) b.push_back(cnt), cnt=0;
if (b.size()!=row[x].size()) return 1;
for (int i=0;i<int(b.size());i++)
if (b[i]!=row[x][i]) return 1;
return 0;
}

int invalidCol(int y)
{
vector <int> b;
int cnt=0;
for (int x=0;x<=m+1;x++)
if (a[x][y]) cnt++;
else
if (cnt) b.push_back(cnt), cnt=0;
if (b.size()!=col[y].size()) return 1;
for (int i=0;i<int(b.size());i++)
if (b[i]!=col[y][i]) return 1;
return 0;
}

int valid()
{
for (int i=1;i<=m;i++)
if (invalidRow(i)) return 0;
for (int i=1;i<=n;i++)
if (invalidCol(i)) return 0;
return 1;
}

int main()
{
int x,y,t;
cin >> m >> n;
for (int i=1;i<=m;i++)
{
row[i].clear();
cin >> y;
while (y--) cin >> x, row[i].push_back(x);
}
for (int i=1;i<=n;i++)
{
col[i].clear();
cin >> y;
while (y--) cin >> x, col[i].push_back(x);
}
cin >> t;
while (t--)
{
for (int i=1;i<=m;i++)
{
string s;
cin >> s;
for (int j=1;j<=n;j++) a[i][j]=(s[j-1]=='1');
}
cout << (valid()?"YES":"NO") << endl;
}
return 0;
}


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 35

vvi con; //constraint
int m, n;
char a[35][35], b[35][35];

void analysis(char a[35][35], int m, int n, vvi &ana) {
rep(i,m) {
ana.pb(vi());
for(char * st = strchr(a[i],'1'); st != NULL;) {
char * en = strchr(st,'0');
if(en != NULL) {
ana.back().pb(en-st);
st = strchr(en,'1');
} else {
ana.back().pb(n-(st-a[i]));
st = NULL;
}
}
}
}

bool ok() {
vvi ana; //analysis
analysis(a, m, n, ana);
rep(i,m) rep(j,n) b[j][i] = a[i][j];
analysis(b, n, m, ana);
return ana == con;
}

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&m,&n);
rep(i,m+n) {
con.pb(vi());
int k;
scanf("%d",&k);
rep(j,k) {
int x; scanf("%d",&x);
con.back().pb(x);
}
}
int t; scanf("%d",&t);
while(t--) {
rep(i,m) scanf("%s",a[i]);
printf(ok() ? "YES\n" : "NO\n");
}
return 0;
}


#### Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#include <sstream>
#include <iomanip>
using namespace std;

const int MAXN = 100;

int nRow, nCol;
vector<int> row[MAXN], col[MAXN];
string solution[MAXN];

bool equal(vector<int> a, vector<int> b) {
if (a.size() != b.size()) return false;

for(int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) return false;
}
return true;
}

int get() {
for(int i = 1; i <= nRow; i++)
if (solution[i].length() != nCol + 1) return 0;

for(int i = 1; i <= nRow; i++) {
for(int j = 1; j <= nCol; j++)
if (solution[i][j] < '0' || solution[i][j] > '1') return 0;
}

int res = 0;

for(int i = 1; i <= nRow; i++) {
string now = solution[i];
for(int x = 0; x < now.length(); x++)
if (now[x] == '0') now[x] = ' ';
istringstream sin(now);
vector<int> cur;
string u;
while (sin >> u) {
cur.push_back(u.length());
}
if (equal(cur, row[i])) res++;
}

for(int j = 1; j <= nCol; j++) {
string now = "";
for(int i = 1; i <= nRow; i++)
now = now + solution[i][j];
for(int x = 0; x < now.length(); x++)
if (now[x] == '0') now[x] = ' ';
istringstream sin(now);
vector<int> cur;
string u;
while (sin >> u) {
cur.push_back(u.length());
}
if (equal(cur, col[j])) res++;
}
return (res == nRow + nCol);
}

cin >> nRow >> nCol;

int sumRow = 0, sumCol = 0;
for(int i = 1; i <= nRow; i++) {
int k;
cin >> k;
while (k--) {
int u;
cin >> u;
row[i].push_back(u);
sumRow += u;
}
}

for(int j = 1; j <= nCol; j++) {
int k; cin >> k;
while (k--) {
int u; cin >> u;
col[j].push_back(u);
sumCol += u;
}
}
}

for(int i = 1; i <= nRow; i++) {
string tmp;
cin >> tmp;
solution[i] = " ";

for(int x = 0; x < tmp.length(); x++) {
if (tmp[x] != '0' && tmp[x] != '1') {
return false;
}
solution[i] += tmp[x];
}
}
return get();
}

int main() {
int t; cin >> t;
while (t--) {
else puts("NO");
}
return 0;
}


#### Code mẫu của hieult

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
//#include <conio.h>
//double const PI=4*atan(1);

int a[33],b[33],A[33][33],B[33][33],m,n,test,x[33],so;
bool check;
char s[33][33];

using namespace std;

int main(){
// freopen("MAKHOA3.in","r",stdin);
// freopen("A.out","w",stdout);
scanf("%d %d",&m,&n);
for(int i = 1;i<=m;i++){
scanf("%d",&a[i]);
for(int j = 1;j<=a[i];j++)
scanf("%d",&A[i][j]);
}
for(int i = 1;i<=n;i++){
scanf("%d",&b[i]);
for(int j = 1;j<=b[i];j++)
scanf("%d",&B[i][j]);
}
scanf("%d",&test);
for(int itest = 1;itest<=test;itest++){
check = true;
for(int i = 0;i<m;i++){
scanf("%s",s[i]);
// printf("%s\n",s[i]);
so = 0;
//printf("***%d*** %d\n",s[0][3],s[i][0]=='1');
if(s[i][0]=='1'){
//  printf("??\n");
x[++so]=1;
}
for(int j = 1;j<n;j++){
if(s[i][j]=='1'){
if(s[i][j-1]=='0') x[++so] = 1;
else x[so]++;
}
}
if(so!=a[i+1]) { check = false;}
else{
for(int j = 1;j<=so;j++)
if(A[i+1][j]!=x[j]){
check = false;
}
}
}
for(int i = 0;i<n;i++){
so = 0;
if(s[0][i]=='1'){
x[++so]=1;
}
for(int j = 1;j<m;j++){
if(s[j][i]=='1'){
if(s[j-1][i]=='0') x[++so] = 1;
else x[so]++;
}
}
if(so!=b[i+1]){ check = false;}
else{
for(int j = 1;j<=so;j++)
if(B[i+1][j]!=x[j]){
check = false;
}
}
}
if(check) printf("YES\n");
else printf("NO\n");
}
//  getch();
}