QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#536276#8651. Table Tennislfyszy0 1ms6016kbC++142.7kb2024-08-28 22:08:352024-08-28 22:08:35

Judging History

你现在查看的是最新测评结果

  • [2024-08-28 22:08:35]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:6016kb
  • [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%