Problem
You are given an integer . Generate a matrix of size such that:
- Each element of the matrix is either
0
or1
; - All rows (from left to right) and all columns (from top to bottom) are distinct.
In other words, the strings, that are obtained from the rows and columns of the matrix, are all distinct.
If multiple such matrices exist, print any. If no such matrix exists, print instead.
Input Format
- The first line of input will contain a single integer , denoting the number of test cases.
- Each test case consists of a single integer , the length of the row and column of matrix.
Output Format
For each test case, output lines, where each line contains a binary string of length , such that the matrix satisfies the given conditions.
If no such matrix exists, print .
Constraints
- The sum of over all test cases won't exceed .
Sample 1:
3 4 2 5
1010 1110 1001 1011 -1 00101 11010 01110 11001 01011
Explanation:
Test case : The rows of the matrix are . The columns of the matrix are .
The set of all rows and columns are . Note that all elements of the set containing all rows and columns are distinct. Thus, the matrix satisfies the conditions.
Test case : It can be proven that no binary matrix of size is valid.
Solution :
Make a matrix like this
100000...00
110000...00
111000...00
...
111111...10
111111...11
Now analyze which row and column are same.
#include <bits/stdc++.h>using namespace std;#define int long long int#define F first#define S second#define pb push_back#define si set <int>#define vi vector <int>#define pii pair <int, int>#define vpi vector <pii>#define vpp vector <pair<int, pii>>#define mii map <int, int>#define mpi map <pii, int>#define spi set <pii>#define endl "\n"#define sz(x) ((int) x.size())#define all(p) p.begin(), p.end()#define double long double#define que_max priority_queue <int>#define que_min priority_queue <int, vi, greater<int>>#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)#define print(a) for(auto x : a) cout << x << " "; cout << endl#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endlinline int power(int a, int b){int x = 1;while (b){if (b & 1) x *= a;a *= a;b >>= 1;}return x;}template <typename Arg1>void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }template <typename Arg1, typename... Args>void __f (const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr (names + 1, ',');cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);}const int N = 200005;void solve() {int n;cin>>n;if(n<=2){cout<<-1<<endl;return;}vector<vi>ans;for (int i = 0; i < n; i++){vi temp;for (int j = 0; j < n; j++){if(j<=i)temp.push_back(1);else temp.pb(0);}ans.pb(temp);}ans[1][0]=0;//print the answerfor (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cout<<ans[i][j];}cout<<endl;}}int32_t main(){ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);clock_t z = clock();int t = 1;cin >> t;while (t--) solve();return 0;}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.