QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370876#7943. LIS on GridvioalbertRE 1ms3772kbC++143.1kb2024-03-29 18:26:392024-03-29 18:26:40

Judging History

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

  • [2024-03-29 18:26:40]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3772kb
  • [2024-03-29 18:26:39]
  • 提交

answer

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

#define rep(i, n, N) for (int i = (n); i <= (N); i++)
#define For(i, n, N) for (int i = (n); i <  (N); i++)
#define rap(i, n, N) for (int i = (n); i >= (N); i--)
#define rip(i, n, N, V) for (int i = (n); i <= (N); i += V)

using vi = vector<int>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
using plll = pair<lll, lll>;

#define fi first
#define se second
#define ff fi.fi
#define fs fi.se
#define sf se.fi
#define ss se.se
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front

#define endl '\n'
#define clz(x) (1 << (31 - __builtin_clz(x)))
#define all(x) x.begin(), x.end()
#define ari(x) array<int, x>
#define arll(x) array<ll, x>
#define mems(x, y) memset(x, y, sizeof x)
#define debug(x) cout << #x << " = " << (x) << endl
#define debugV(v, x) cout << #v << "[" << (x) << "] = " << v[x] << endl
#define out(x, y) cout << "]] " << (x) << " " << (y) << endl

#ifdef LOCAL
#define DEBUG(...) __VA_ARGS__;
#else
#define DEBUG(...)
#endif

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
  return os << "(" << p.fi << ", " << p.se << ")";
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
  os << "{"; bool osu = 1;
  for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
  return os << "}";
}
template<class T, ull sz>
ostream& operator<<(ostream& os, const array<T, sz> &v) {
  os << "{"; bool osu = 1;
  for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
  return os << "}";
}

int check(const vector<vi> &g) {
  int n = g.size(), m = g[0].size();
  vector<vi> val(n, vi(m));
  For(i, 0, n) val[i][0] = g[i][0];
  For(j, 1, m) {
    int mx = 0;
    For(i, 0, n) {
      val[i][j] = mx + g[i][j];
      mx = max(mx, val[i][j-1]);
    }
  }
  int ans = 0;
  For(i, 0, n) For(j, 0, m) ans = max(ans, val[i][j]);
  return ans;
}

void solve(int tt = 0) {
  int n, m; cin >> n >> m;
  vi a(m);
  for(int &i : a) cin >> i;
  int k = min(n, m);

  ll sum = 0;
  for(int i : a) sum += max(0, i-k);
  while(k > 0 && sum <= (ll)k * (n-k)) {
    k--;
    sum = 0;
    for(int i : a) sum += max(0, i-k);
  }
  k++;

  vector<vi> grid(n, vi(m));
  cout << k << '\n';

  vi b(m);
  For(i, 0, m) b[i] = max(0, a[i] - k);
  
  For(s, 0, k) {
    int r = n - k + s;
    For(j, 0, m) {
      grid[r][j] = 1;
      while(r > 0 && b[j] > 0 && grid[r-1][j] == 0) {
        b[j]--;
        r--;
        grid[r][j] = 1;
      }
    }
  }

  For(j, 0, m) if(a[j] < k) {
    int hv = k - a[j];
    For(i, 0, n) {
      if(grid[i][j]) {
        grid[i][j] = 0;
        hv--;
      }
      if(hv == 0) break;
    }
  }

  For(i, 0, n) For(j, 0, m) {
    cout << (grid[i][j] ? '#' : '.');
    if(j+1 == m) cout << '\n';
  }

  assert(check(grid) == k);
}

int main() {
  int t; cin >> t;
  rep(ct, 1, t) solve(ct);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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: