QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#536276 | #8651. Table Tennis | lfyszy | 0 | 1ms | 6016kb | C++14 | 2.7kb | 2024-08-28 22:08:35 | 2024-08-28 22:08:35 |
answer
// problem:
// date:
#include <bits/stdc++.h>
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 10;
int res[N][N], inq[N];
vector<int> du[N];
queue<int> q;
#define c2(n) (n * (n - 1) / 2)
#define c3(n) (n * (n - 1) * (n - 2) / 6)
int min_m(int n) {return n & 1 ? n * c2(n / 2) : (n / 2) * c2(n / 2) + (n / 2) * c2(n / 2 - 1);}
void solve()
{
int n, m; cin >> n >> m;
/*-----*/
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
res[i][j] = 0;
for(int i = 0; i < n; i ++) inq[i] = 0;
for(int i = 0; i < n; i ++) du[i].clear();
while(q.size()) q.pop();
/*-----*/
m = c3(n) - m;
if(min_m(n) > m || m > c3(n)) {cout << "No\n"; return ;}
int sum = 0, tp = n;
while(tp && min_m(tp - 1) + c2(tp - 1) + sum <= m) sum += c2(tp - 1), tp --;
int k = min_m(tp) + sum;
// cout << tp SP n SP k SP m << "\n";
for(int i = 1; i <= tp; i ++)
{
if(tp & 1)
{
int j = i + 1;
for(int o = 1; o <= tp / 2; o ++)
{
if(j > tp) j = 1;
res[i][j] = 1, j ++;
}
}
else
{
int j = i + 1;
for(int o = 1; o <= tp / 2 - (i > tp / 2); o ++)
{
res[i][j] = 1, j ++;
if(j > tp) j = 1;
}
}
}
for(int i = tp + 1; i <= n; i ++)
for(int j = 1; j < i; j ++) res[i][j] = 1;
for(int i = 1; i <= n; i ++)
{
int d = 0;
for(int j = 1; j <= n; j ++) d += res[i][j];
du[d].push_back(i);
}
for(int d = 0; d < n; d ++)
if(du[d].size() >= 2)
inq[d] = 1, q.push(d);
for(; k < m; k ++)
{
int d = q.front(); q.pop();
inq[d] = 0;
int u = du[d].back(); du[d].pop_back();
int v = du[d].back(); du[d].pop_back();
swap(res[u][v], res[v][u]);
if(res[u][v] == 1) swap(u, v);
du[d - 1].push_back(u);
du[d + 1].push_back(v);
for(int i = d - 1; i <= d + 1; i ++)
if(du[i].size() >= 2)
inq[i] = 1, q.push(i);
}
cout << "Yes\n";
for(int i = 1; i <= n; i ++)
for(int j = 1; j < i; j ++)
cout << res[i][j] << (j == i - 1 ? "\n" : "\0");
}
fish main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t --) solve();
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
97 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 61 0 62 0 63 0...
output:
Yes 0 11 No
result:
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 4
Accepted
time: 1ms
memory: 3972kb
input:
1 4 4
output:
No
result:
ok good job! (1 test case)
Test #59:
score: 4
Accepted
time: 0ms
memory: 3628kb
input:
1 5 10
output:
No
result:
ok good job! (1 test case)
Test #60:
score: 4
Accepted
time: 0ms
memory: 3740kb
input:
1 6 20
output:
No
result:
ok good job! (1 test case)
Test #61:
score: 4
Accepted
time: 0ms
memory: 3924kb
input:
1 7 35
output:
No
result:
ok good job! (1 test case)
Test #62:
score: 4
Accepted
time: 0ms
memory: 3756kb
input:
1 5 10
output:
No
result:
ok good job! (1 test case)
Test #63:
score: 4
Accepted
time: 0ms
memory: 3636kb
input:
1 6 19
output:
No
result:
ok good job! (1 test case)
Test #64:
score: 4
Accepted
time: 0ms
memory: 5980kb
input:
1 6 20
output:
No
result:
ok good job! (1 test case)
Test #65:
score: 4
Accepted
time: 0ms
memory: 4008kb
input:
1 7 33
output:
No
result:
ok good job! (1 test case)
Test #66:
score: 4
Accepted
time: 1ms
memory: 3920kb
input:
1 7 33
output:
No
result:
ok good job! (1 test case)
Test #67:
score: 4
Accepted
time: 0ms
memory: 3744kb
input:
1 4 3
output:
No
result:
ok good job! (1 test case)
Test #68:
score: 4
Accepted
time: 1ms
memory: 6016kb
input:
1 5 8
output:
No
result:
ok good job! (1 test case)
Test #69:
score: 4
Accepted
time: 0ms
memory: 3720kb
input:
1 6 17
output:
No
result:
ok good job! (1 test case)
Test #70:
score: 4
Accepted
time: 0ms
memory: 3964kb
input:
1 7 30
output:
No
result:
ok good job! (1 test case)
Test #71:
score: 4
Accepted
time: 0ms
memory: 3728kb
input:
2 3 0 3 1
output:
Yes 0 11 Yes 0 10
result:
ok good job! (2 test cases)
Test #72:
score: 4
Accepted
time: 0ms
memory: 3744kb
input:
2 3 0 3 1
output:
Yes 0 11 Yes 0 10
result:
ok good job! (2 test cases)
Test #73:
score: 0
Wrong Answer
time: 0ms
memory: 3936kb
input:
1 4 2
output:
No
result:
wrong answer you did't find a solution but jury did (test case 1)
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%