#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
ll n, m;
cin >> n >> m;
m = n * (n - 1) * (n - 2) / 6 - m;
auto c2 = [&](ll a){
return a * (a - 1) / 2;
};
vector<ll> deg(n + 1, -1);
ll cur = 0, tar = c2(n), cur2 = 0;
bool flag = 1;
for(int i = 1; i < n; i++){
for(ll j = 0; j < n; j++){
if(cur + j < c2(i)) continue;
ll rest = tar - cur - j, rm = m - cur2 - c2(j), rn = n - i;
ll mini = c2(rest / rn) * (rn - (rest % rn)) + c2(rest / rn + 1) * (rest % rn);
if(mini > rm) continue;
deg[i] = j;
cur += j;
cur2 += c2(j);
break;
}
if(deg[i] == -1){
flag = 0;
break;
}
}
deg[n] = tar - cur;
if(cur2 + c2(deg[n]) != m || deg[n] >= n || deg[n] < 0) flag = 0;
//for(int i = 1; i <= n; i++) cout << deg[i] << "\n";
if(flag){
cout << "Yes\n";
sort(next(deg.begin()), deg.end());
vector<vector<int>> ans(n + 1, vector<int>(n + 1));
vector<pair<int, int>> degs;
for(int i = 1; i <= n; i++) degs.emplace_back(deg[i], i);
for(int i = n; i > 0; i--){
sort(degs.begin(), degs.end());
auto [val, id] = degs.back();
degs.pop_back();
for(int j = 0; j < (int)degs.size(); j++){
auto &[val2, id2] = degs[j];
if(j < val) ans[id][id2] = 1;
else{
ans[id2][id] = 2;
val2--;
}
}
}
ll sum = 0;
for(int i = 1; i <= n; i++) sum += c2(deg[i]);
assert(sum == m);
for(int i = 2; i <= n; i++){
for(int j = 1; j < i; j++) cout << ans[i][j];
cout << "\n";
}
}
else cout << "No\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
7 ms |
592 KB |
Output is correct |
| 3 |
Correct |
493 ms |
104008 KB |
Output is correct |
| 4 |
Correct |
138 ms |
12228 KB |
Output is correct |
| 5 |
Correct |
153 ms |
16392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1872 KB |
Output is correct |
| 13 |
Correct |
8 ms |
1872 KB |
Output is correct |
| 14 |
Correct |
563 ms |
111172 KB |
Output is correct |
| 15 |
Correct |
559 ms |
111192 KB |
Output is correct |
| 16 |
Incorrect |
3 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
508 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
424 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
508 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
424 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
508 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
424 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
508 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
424 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
7 ms |
592 KB |
Output is correct |
| 3 |
Correct |
493 ms |
104008 KB |
Output is correct |
| 4 |
Correct |
138 ms |
12228 KB |
Output is correct |
| 5 |
Correct |
153 ms |
16392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1872 KB |
Output is correct |
| 13 |
Correct |
8 ms |
1872 KB |
Output is correct |
| 14 |
Correct |
563 ms |
111172 KB |
Output is correct |
| 15 |
Correct |
559 ms |
111192 KB |
Output is correct |
| 16 |
Incorrect |
3 ms |
336 KB |
Number of trilema is 5, but expected 6 |
| 17 |
Halted |
0 ms |
0 KB |
- |
