QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648151#7943. LIS on GridhezlikWA 7ms3640kbC++202.6kb2024-10-17 17:18:352024-10-17 17:18:40

Judging History

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

  • [2024-10-17 17:18:40]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3640kb
  • [2024-10-17 17:18:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve() {
  int n, m;
  cin >> m >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  vector<vector<int>> pre(n + 1, vector<int>(m));
  for (int i = 0; i < n; i++) {
    int mx = 0;
    for (int j = 0; j < m; j++) {
      if (j >= m - a[i]) {
        pre[i + 1][j] = mx + 1;
      }
      pre[i + 1][j] = max(pre[i + 1][j], pre[i][j]);
      mx = max(mx, pre[i][j]);
    }
  }
  vector<vector<int>> suf(n + 1, vector<int>(m));
  for (int i = n - 1; i >= 0; i--) {
    int mx = 0;
    for (int j = m - 1; j >= 0; j--) {
      if (j < a[i]) {
        suf[i][j] = mx + 1;
      }
      suf[i][j] = max(suf[i][j], suf[i + 1][j]);
      mx = max(mx, suf[i + 1][j]);
    }
  }

  int ans = INF;
  for (int i = 1; i < n; i++) {
    vector<int> suf_mx(m + 1);
    for (int j = m - 1; j >= 0; j--)
      suf_mx[j] = max(suf_mx[j + 1], suf[i][j]);
    int cut = suf_mx[0];
    for (int j = 0; j < m; j++) {
      cut = max(cut, pre[i][j] + suf_mx[j + 1]);
    }
    ans = min(ans, cut);
  }
  int cut0 = 0, cutn = 0;
  for (int j = 0; j < m; j++) {
    cut0 = max(cut0, pre[n][j]);
    cutn = max(cutn, suf[0][j]);
  }
  ans = min(ans, cut0);
  ans = min(ans, cutn);

  cout << ans << "\n";
  for (int i = 1; i < n; i++) {
    vector<int> suf_mx(m + 1);
    for (int j = m - 1; j >= 0; j--)
      suf_mx[j] = max(suf_mx[j + 1], suf[i][j]);
    int cut = suf_mx[0];
    for (int j = 0; j < m; j++) {
      cut = max(cut, pre[i][j] + suf_mx[j + 1]);
    }
    // for (int j = 0; j < m; j++) {
    //   if (cut == pre[i][j] + suf_mx[j + 1]) {
    //     cout << "!!!" << i << " " << j << " " << endl;
    //   }
    // }
    if (cut == ans) {
      // cout << "!!!" << i << " " << cut << endl;
      for (int k = 0; k < m; k++) {
        for (int l = 0; l < i; l++) {
          cout << ".#"[k >= m - a[l]];
        }
        for (int l = i; l < n; l++) {
          cout << ".#"[k < a[l]];
        }
        cout << "\n";
      }
      return;
    }
  }

  if (ans == cut0) {
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        cout << ".#"[i >= m - a[j]];
      }
      cout << "\n";
    }
    return;
  }
  if (ans == cutn) {
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        cout << ".#"[i < a[j]];
      }
      cout << "\n";
    }
    return;
  }

  assert(0);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

/*

1
5 5
4 5 1 3 5

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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
.###
.###
##..
3
.#.##
.#.##
.####
#####
###..
2
#####
#..#.
#..#.
#..#.
3
..###
..###
##.##
##.##
##.##
2
.####
..#..
#.#..
#....
#....
2
..###
.####
.###.
###..
##...
2
.####
.####
#....
#....
3
.####
####.
###...

result:

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