QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393675#7943. LIS on Gridkyuukyuusha#WA 1ms3628kbC++172.0kb2024-04-19 06:34:182024-04-19 06:34:18

Judging History

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

  • [2024-04-19 06:34:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3628kb
  • [2024-04-19 06:34:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

bool check(int m, vector<vector<bool>> &grid, vector<int> a) {
    int l = 0, r = 0;
    // cout << m << endl;
    
    for (r = 0; r < a.size() + grid.size() - 1; ++r) {
        int marks = m;
        for(int b = l; b <= r && b <= a.size()-1 && marks > 0; ++b) {
            if (a[b] > 0) {
                grid[grid.size()-r+b-1][b] = true;
                --a[b];
                --marks;
            }
            // cout << l << " " << r << endl;
            // for (int i = 0; i < grid.size(); ++i) {
            //     for (int j = 0; j < grid[0].size(); ++j) {
            //         cout << (grid[i][j] ? '#' : '.');
            //     }
            //     cout << endl;
            // }
        }
        while(a[l] <= 0 && l <= r && l <= a.size() - 1) {
            ++l;
        }
        if ((r-l)+1 >= grid.size()) {
            // cout << "NO" << endl;
            return false;
        }
    }
    return true;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        int smaller = min(n, m);
        vector<int> a(m);
        for (int i = 0; i < m; ++i) {
            cin >> a[i];
        }
        int l = 0, r = smaller, mi;
        vector<vector<bool>> grid(n, vector<bool>(m,false));
        while (l<r) {
            mi = l+(r-l)/2;
            grid = vector<vector<bool>>(n, vector<bool>(m, false));
            if(check(mi, grid, a)) {
                r = mi;
            } else {
                l = mi+1;
            }
        }
        cout << l << endl;
        grid = vector<vector<bool>>(n, vector<bool>(m, false));
        check(l, grid, a);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (grid[i][j] ? '#' : '.');
            }
            cout << endl;
        }
    }
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3628kb

input:

4
2 4
1 1 1 1
3 3
3 3 3
4 4
4 3 2 1
4 5
2 3 4 3 2

output:

1
....
####
3
###
###
###
2
#.#.
###.
##.#
##..
2
..###
.####
####.
###..

result:

wrong answer Wrong score (test case 3)