QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#614706#5438. Half Mixedmhw#RE 147ms11516kbC++202.8kb2024-10-05 16:50:282024-10-05 16:50:28

Judging History

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

  • [2024-10-05 16:50:28]
  • 评测
  • 测评结果：RE
  • 用时：147ms
  • 内存：11516kb
查看
  • [2024-10-05 16:50:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
const int maxn = 100;
const int N = 1e6 + 7;
int f[51][200]{};
ll w[1000010];
int n, m;
int work(ll tot, int tp)
{
    vector<int> ans;

    ll W = (tot + 1) * tot / 4;
    ll V = tot;

    if (W < V){
        cout << "No\n";
        return -1;
    }

    while (W && V)
    {
        if (W < maxn)
            break;
        int id = upper_bound(w + 1, w + 1000001, min(W, W - V)) - w - 1; // 小于等于min(W, W + 1 - V)的
        W -= w[id] + id;
        V -= id;
        ans.push_back(id);
    }


    // W 填充的 W < maxn && W >= V
    // V 格子数
    while (W > 0 && V > 0)
    {
        int t = f[V][W];
        if(t == -1){
            cout << "No\n";
            return -1;
        }
        ll dt = t * (t + 1) / 2;
        ans.push_back(t);
        W -= dt, V -= t;
    }

    cout << "Yes\n";
    if (tp == 1)
    {
        int now = 0;
        for (auto x : ans)
        {
            for (int j = 1; j <= x; ++j)
            {
                for (int i = 1; i <= m; ++i)
                    cout << now << " ";
                cout << '\n';
            }
            now ^= 1;
            
        }
        return 1;
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            int now = 0;
            for (auto x : ans)
            {
                for (int j = 1; j <= x; ++j)
                {
                    cout << now << " ";
                }
                now ^= 1;
            }
            cout << '\n';
        }
        return 1;
    }
}
void slv()
{
    int op = -1;
    cin >> n >> m;

    if (n % 4 == 0 || n % 4 == 3){
        op = n;
        if(work(n, 1) == 1) return;
    }
    if (m % 4 == 0 || m % 4 == 3){
        op = m;
        if(work(m, 2) == 1) return;
    }

    if (op == -1)
    {
        cout << "No\n";
        return;
    }
    return ;
}

void init()
{

    for (int i = 1; i <= 1000000; ++i)
        w[i] = (i + 1) * i / 2 - i;

    memset(f, -1, sizeof(f));
    vector<int> g(51);
    g[0] = 0;
    for (int i = 1; i <= 50; i++)
    {
        g[i] = i * (i + 1) / 2;
    }
    f[0][0] = 0;
    for (int i = 0; i <= 50; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            if (f[i][j] == -1)
                continue;
            for (int k = 0; k <= 50; k++)
            {
                if (j + g[k] < 101 && i + k < 50)
                {
                    f[i + k][j + g[k]] = max(f[i + k][j + g[k]], k);
                }
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    init();
    int _;
    cin >> _;
    while (_--)
        slv();
}
/*
3
2 3
3 2
1 1
*/
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11508kb

input:

2
2 3
1 1

output:

Yes
0 1 0 
0 1 0 
No

result:

ok OK, Accepted. (2 test cases)

Test #2:

score: 0
Accepted
time: 147ms
memory: 11516kb

input:

5382
1 1
1 2
2 1
1 3
2 2
3 1
1 4
2 3
3 2
4 1
1 5
2 4
3 3
4 2
5 1
1 6
2 5
3 4
4 3
5 2
6 1
1 7
2 6
3 5
4 4
5 3
6 2
7 1
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
9 1
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1
1 11
2 10
3 9
4 8
5 7
6 6
7 5
8 4
9 3
10 2
11 1
1 12
2 11
3 10
4 9
5 8
6 ...

output:

No
No
No
Yes
0 1 0 
No
Yes
0 
1 
0 
Yes
0 0 1 0 
Yes
0 1 0 
0 1 0 
Yes
0 0 
1 1 
0 0 
Yes
0 
0 
1 
0 
No
Yes
0 0 1 0 
0 0 1 0 
Yes
0 0 0 
1 1 1 
0 0 0 
Yes
0 0 
0 0 
1 1 
0 0 
No
No
No
Yes
0 0 0 0 
1 1 1 1 
0 0 0 0 
Yes
0 0 0 
0 0 0 
1 1 1 
0 0 0 
No
No
Yes
0 0 0 0 1 1 0 
No
Yes
0 0 0 0 0 
1 1 1 1 1...

result:

ok OK, Accepted. (5382 test cases)

Test #3:

score: 0
Accepted
time: 131ms
memory: 11496kb

input:

1177
50 50
50 51
51 50
50 52
51 51
52 50
50 53
51 52
52 51
53 50
50 54
51 53
52 52
53 51
54 50
50 55
51 54
52 53
53 52
54 51
55 50
50 56
51 55
52 54
53 53
54 52
55 51
56 50
50 57
51 56
52 55
53 54
54 53
55 52
56 51
57 50
50 58
51 57
52 56
53 55
54 54
55 53
56 52
57 51
58 50
50 59
51 58
52 57
53 56
5...

output:

No
Yes
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1...

result:

ok OK, Accepted. (1177 test cases)

Test #4:

score: 0
Accepted
time: 137ms
memory: 11512kb

input:

420
100 100
100 101
101 100
100 102
101 101
102 100
100 103
101 102
102 101
103 100
100 104
101 103
102 102
103 101
104 100
100 105
101 104
102 103
103 102
104 101
105 100
100 106
101 105
102 104
103 103
104 102
105 101
106 100
100 107
101 106
102 105
103 104
104 103
105 102
106 101
107 100
100 108
...

output:

Yes
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

result:

ok OK, Accepted. (420 test cases)

Test #5:

score: -100
Runtime Error

input:

6
900 900
900 901
901 900
900 902
901 901
902 900

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-02 23:43:57 | 开源项目