QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392782#7943. LIS on Griducup-team3215#WA 8ms3632kbC++202.4kb2024-04-17 20:30:392024-04-17 20:30:40

Judging History

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

  • [2024-04-17 20:30:40]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3632kb
  • [2024-04-17 20:30:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (auto &i: a)cin >> i;
    int lres = 0, rres = n * m + 2;
    while (rres - lres > 1) {
        int mid = (rres + lres) / 2;
//        mid = 2;
        bool ok{true};
        vector<int> dp(n, 0);
        for (int i = 0; i < m; ++i) {
            int l = -1, r = n - a[i] + 1;
            while (r - l > 1) {
                int mm = (r + l) / 2;
                int cur = (mm ? dp[mm - 1] : dp[mm]);
                int mx = cur;
                for (int j = 0; j < a[i]; ++j) {
                    mx = max(mx, cur + 1);
                    if (j + 1 < a[i])cur = max(cur, dp[mm + j]);
                }
                if (mx <= mid) {
                    l = mm;
                } else r = mm;
            }
            if (~l) {
                for (int j = a[i] - 1; ~j; --j) {
                    dp[l + j] = max(dp[l + j], (l + j - 1 >= 0 ? dp[l + j - 1] : 0) + 1);
                }
                for (int j = 1; j < n; ++j)dp[j] = max(dp[j], dp[j - 1]);
            } else {
                ok = false;
                break;
            }
        }
        if (ok) {
            rres = mid;
        } else lres = mid;
    }
//    cout << rres << "\n";
    vector<int> dp(n, 0);
    vector<vector<char>> res(n, vector<char>(m, '.'));
    for (int i = 0; i < m; ++i) {
        int l = -1, r = n - a[i] + 1;
        while (r - l > 1) {
            int mm = (r + l) / 2;
            int cur = (mm ? dp[mm - 1] : dp[mm]);
            int mx = cur;
            for (int j = 0; j < a[i]; ++j) {
                mx = max(mx, cur + 1);
                if (j + 1 < a[i])cur = max(cur, dp[mm + j]);
            }
            if (mx <= rres) {
                l = mm;
            } else r = mm;
        }
        assert(~l);
        for (int j = a[i] - 1; ~j; --j) {
            dp[l + j] = max(dp[l + j], (l + j - 1 >= 0 ? dp[l + j - 1] : 0) + 1);
            res[l + j][i] = '#';
        }
        for (int j = 1; j < n; ++j)dp[j] = max(dp[j], dp[j - 1]);
    }
    cout << rres << "\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << res[i][j];
        }
        cout << "\n";
    }

}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

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:

ok Correct (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 8ms
memory: 3632kb

input:

5699
5 5
4 5 1 3 5
4 4
3 1 2 4
5 5
2 2 3 3 4
3 4
1 3 2 2
5 5
2 5 3 4 4
4 5
4 1 1 4 1
5 5
3 3 2 5 5
5 5
3 1 3 1 1
5 5
2 4 4 3 2
4 5
2 2 2 2 2
5 5
4 5 3 4 1
5 4
5 4 1 4
5 4
1 1 1 3
4 2
2 4
5 5
2 5 5 2 5
5 5
5 1 2 1 3
5 5
4 4 2 2 3
5 2
5 2
3 5
2 3 3 1 3
5 5
4 2 5 1 1
5 5
4 5 4 1 5
5 4
3 2 5 3
5 5
5 4 1...

output:

4
.#..#
##..#
##.##
##.##
#####
3
...#
#..#
#.##
####
2
....#
....#
..###
#####
####.
2
.#.#
.###
###.
3
.#..#
.#.##
.####
#####
####.
2
#..#.
#..##
#..#.
####.
3
...##
...##
##.##
#####
#####
2
.....
.....
#.#..
#.###
###..
2
...#.
.####
.####
###..
###..
2
.....
.....
#####
#####
3
.#.#.
##.#.
###...

result:

wrong answer Jury found better answer than participant (test case 1)