# Atcoder starter competition 164 f I Hat Matrix Construction + fixed row modification column

Atcoder starter competition 164 number of competitors 11302 see all questions 15 minutes after the start of the competition

Atcoder starter competition 164 F I Hat Matrix Construction + fixed row modification column

See the general catalog for details https://blog.csdn.net/mrcrack/article/details/104454762

Core idea:

If the result of 1 column of data is 0 after and operation, then the value of this column of data contains at least one 0

If the result of a column of data is 1 after operation, then the values of this column of data are all 1

If the result of 1 column of data is 0 after or operation, then the values of this column of data are all 0

If the result of a column of data after or operation is 1, then the value of this column of data contains at least one 1

The sample simulation is as follows

```2
1 1
1 0
15 15
15 11

From the row data, get the basic outline of matrix
15 15
15 15

Binary form
1111  1111
1111  1111

One by one, check with column operation
Column 1 1 15 (1111) column 1 through or operation, the result is 15 (1111)

Matrix binary form
1111  1111
1111  1111

The second column 0 11 (1011) the second column after and operation, the result is 11 (1011)

Matrix binary form
1111  1011
1111  1111

Matrix decimal form
15 11
15 15
```

The specific ideas can be seen in the code. I believe that readers can understand it easily if they have the form and pressure basis.

The AC code is as follows

``````#include <stdio.h>
#define ull unsigned long long
#define maxn 505
int s[maxn],t[maxn],br[maxn],bc[maxn],cnt[maxn],a[maxn][maxn];//s[0]:row,and;s[1]:row:or.t[0]:col,and;t[1]:col,or;
ull u[maxn],v[maxn],ans[maxn][maxn];
int main(){
int i,j,n,k;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&s[i]);
for(i=1;i<=n;i++)scanf("%d",&t[i]);
for(i=1;i<=n;i++)scanf("%llu",&u[i]);
for(i=1;i<=n;i++)scanf("%llu",&v[i]);
for(k=0;k<64;k++){//Bit by bit determination
for(i=1;i<=n;i++)br[i]=((u[i]>>k)&1),bc[i]=((v[i]>>k)&1);//Get the value at k
int hr[4]={0,0,0,0},hc[4]={0,0,0,0};//hr{(row,and,0),(row,and,1),(row,or,0),(row,or,1)} statistics quantity
for(i=1;i<=n;i++)//Row and column calculation
hr[s[i]*2+br[i]]++,hc[2*t[i]+bc[i]]++;//hc{(col,and,0),(col,and,1),(col,or,0),(col,or,1)}
if(hr[2]&&hc[1])return 0*printf("-1\n");//Row, or, 0, (col, and, 1), both cannot have values at the same time
if(hc[2]&&hr[1])return 0*printf("-1\n");//Coarse screen (col,or,0),(row,and,1), both of which cannot have values at the same time
for(i=1;i<=n;i++){//Set the initial value with the value after line operation
cnt[i]=n;//On line i, there are n identical data
for(j=1;j<=n;j++)
a[i][j]=br[i];//The reasons can be set as follows: 1 & 1 = 1,0 & 0 = 0; 1|1 = 1,0|0 = 0;
}
for(j=1;j<=n;j++)//Modify data to meet column requirements
if(t[j]!=bc[j])//t[j] is the k position value of the j-th column operand (0, and; 1, or) recorded by BC [J]. All 1, all 0
for(i=1;i<=n;i++)
if(a[i][j]!=bc[j])cnt[i]--,a[i][j]=bc[j];//The same elements in the same row need to be reduced.
for(j=1;j<=n;j++){//Use the value after column operation to repair
int flag=0;//Determine whether to find
if(t[j]==bc[j]){//(col,and,0,0) or (col,or,1,1)
for(i=1;i<=n;i++)
if(a[i][j]==bc[j]){flag=1;break;}//Find the location of 0 or 1. Just find one.
if(flag)continue;//If found, move on to the next line
for(i=1;i<=n;i++)//Keep looking
if(s[i]==br[i]&&cnt[i]>=2){//s[i] represents the number of operands in line I (0,and;1,or),br[i] records the k position value of the operation result in line I, (0,and,0) has at least one 0;(1,or,1) has at least one 1. CNT [i] > = 2 has at least two identical values
cnt[i]--,a[i][j]=bc[j];//It can be changed because there are at least two similarities
break;
}
}
//There's a situation where I've made a round and I haven't succeeded in making the change. Don't worry. After that, there will be an inspection.
}
for(i=1;i<=n;i++)//Generate pending matrix elements
for(j=1;j<=n;j++)
ans[i][j]|=((ull)a[i][j]<<k);//k processing
}
for(i=1;i<=n;i++){//Line inspection
ull c=ans[i][1];
for(j=2;j<=n;j++)
if(s[i]==0)c=c&ans[i][j];
else c=c|ans[i][j];
if(c!=u[i])return 0*printf("-1\n");
}
for(j=1;j<=n;j++){//Column test
ull c=ans[1][j];
for(i=2;i<=n;i++)
if(t[j]==0)c=c&ans[i][j];
else c=c|ans[i][j];
if(c!=v[j])return 0*printf("-1\n");
}
for(i=1;i<=n;i++){//Tested
for(j=1;j<=n;j++)
printf("%llu ",ans[i][j]);
printf("\n");
}
return 0;
}``````

Added by rob on Tue, 05 May 2020 08:39:36 +0300