QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#285114#7943. LIS on Griducup-team180#WA 6ms3772kbC++171.6kb2023-12-16 16:35:522023-12-16 16:35:54

Judging History

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

  • [2023-12-16 16:35:54]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3772kb
  • [2023-12-16 16:35:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int j = 0; j < m; j++){
      cin >> a[j];
    }
    int tv = n, fv = 0;
    while (tv - fv > 1){
      int mid = (tv + fv) / 2;
      long long sum = 0;
      for (int j = 0; j < m; j++){
        sum += max(a[j] - mid, 0);
      }
      if (sum <= (long long) mid * (n - mid)){
        tv = mid;
      } else {
        fv = mid;
      }
    }
    int P = tv;
    vector<vector<int>> cnt(P, vector<int>(m, 1));
    int r = 0, s = 0;
    for (int j = 0; j < m; j++){
      for (int k = 0; k < max(a[j] - P, 0); k++){
        if (s == n - P){
          r++;
          s = 0;
        }
        cnt[r][j]++;
        s++;
      }
    }
    for (int j = 0; j < m; j++){
      int s = 0;
      for (int k = 0; k < P; k++){
        cnt[k][j] = min(cnt[k][j], a[j] - s);
        s += cnt[k][j];
      }
    }
    vector<int> p(m, 0);
    vector<vector<char>> c(n, vector<char>(m, '.'));
    for (int j = 0; j < P; j++){
      for (int k = m - 1; k >= 0; k--){
        if (k < m - 1){
          p[k] = max(p[k], p[k + 1] - 1);
        }
        for (int l = 0; l < cnt[j][k]; l++){
          c[p[k]][k] = '#';
          p[k]++;
        }
      }
    }
    cout << P << endl;
    for (int j = 0; j < n; j++){
      for (int k = 0; k < m; k++){
        cout << c[j][k];
      }
      cout << '\n';
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

result:

wrong answer Wrong score (test case 16)