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

Online evaluation address https://atcoder.jp/contests/abc164/tasks/abc164_f

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;
}