QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370876 | #7943. LIS on Grid | vioalbert | RE | 1ms | 3772kb | C++14 | 3.1kb | 2024-03-29 18:26:39 | 2024-03-29 18:26:40 |
Judging History
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 .###. ##.#. ###...