QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290796#7943. LIS on Griducup-team902#WA 10ms3728kbC++202.5kb2023-12-25 15:28:282023-12-25 15:28:28

Judging History

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

  • [2023-12-25 15:28:28]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3728kb
  • [2023-12-25 15:28:28]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T &x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

inline bool check(int x, int n, int m, vector<int> &a){
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> sufmax(n + 1, vector<int>(m + 1, 0));
    for(int j = m - 1; ~j; --j){
        int res = a[j];
        for(int i = 0; i < n; ++i){
            if(res && sufmax[i + 1][j + 1] + 1 <= x){
                dp[i][j] = sufmax[i + 1][j + 1] + 1;
                --res;
            }
            else{
                dp[i][j] = sufmax[i + 1][j + 1];
            }
        }
        if(res) return false;
        for(int i = n - 1; ~i; --i){
            sufmax[i][j] = max(sufmax[i + 1][j], dp[i][j]);
        }
    }
    return true;
}

inline void output(int x, int n, int m, vector<int> &a){
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    vector<vector<char>> ans(n, vector<char>(m));
    vector<vector<int>> sufmax(n + 1, vector<int>(m + 1, 0));
    for(int j = m - 1; ~j; --j){
        int res = a[j];
        for(int i = 0; i < n; ++i){
            if(res && sufmax[i + 1][j + 1] + 1 <= x){
                dp[i][j] = sufmax[i + 1][j + 1] + 1;
                --res;
                ans[i][j] = '#';
            }
            else{
                dp[i][j] = sufmax[i + 1][j + 1];
                ans[i][j] = '.';
            }
        }
        if(res) return assert(0);
        for(int i = n - 1; ~i; --i){
            sufmax[i][j] = max(sufmax[i + 1][j], dp[i][j]);
        }
    }
    printf("%d\n", x);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            putchar(ans[i][j]);
        }
        putchar('\n');
    }
}

void solve(){
    int n, m; r(n), r(m);
    vector<int> a;
    for(int i = 0; i < m; ++i){
        int x; r(x);
        a.push_back(x);
    }
    int l = 0, r = min(n, m), ans;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid, n, m, a)){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    output(ans, n, m, a);
}

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T; r(T);
    while(T--){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3684kb

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: 10ms
memory: 3728kb

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:

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

result:

wrong answer Wrong score (test case 1)