QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#392784 | #7943. LIS on Grid | ucup-team3215# | RE | 0ms | 3580kb | C++20 | 2.4kb | 2024-04-17 20:32:36 | 2024-04-17 20:32:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (auto &i: a)cin >> i;
int lres = -1, rres = n * m + 2;
while (rres - lres > 1) {
int mid = (rres + lres) / 2;
bool ok{true};
vector<int> dp(n, 0);
for (int i = 0; i < m; ++i) {
int l = -1, r = n - a[i] + 1;
while (r - l > 1) {
int mm = (r + l) / 2;
int cur = (mm ? dp[mm - 1] : 0);
int mx = cur;
for (int j = 0; j < a[i]; ++j) {
mx = max(mx, cur + 1);
if (j + 1 < a[i])cur = max(cur, dp[mm + j]);
}
if (mx <= mid) {
l = mm;
} else r = mm;
}
if (~l) {
for (int j = a[i] - 1; ~j; --j) {
dp[l + j] = max(dp[l + j], (l + j - 1 >= 0 ? dp[l + j - 1] : 0) + 1);
}
for (int j = 1; j < n; ++j)dp[j] = max(dp[j], dp[j - 1]);
} else {
ok = false;
break;
}
}
if (ok) {
rres = mid;
} else lres = mid;
}
// cout << rres << "\n";
vector<int> dp(n, 0);
vector<vector<char>> res(n, vector<char>(m, '.'));
for (int i = 0; i < m; ++i) {
int l = -1, r = n - a[i] + 1;
while (r - l > 1) {
int mm = (r + l) / 2;
int cur = (mm ? dp[mm - 1] : dp[mm]);
int mx = cur;
for (int j = 0; j < a[i]; ++j) {
mx = max(mx, cur + 1);
if (j + 1 < a[i])cur = max(cur, dp[mm + j]);
}
if (mx <= rres) {
l = mm;
} else r = mm;
}
assert(~l);
for (int j = a[i] - 1; ~j; --j) {
dp[l + j] = max(dp[l + j], (l + j - 1 >= 0 ? dp[l + j - 1] : 0) + 1);
res[l + j][i] = '#';
}
for (int j = 1; j < n; ++j)dp[j] = max(dp[j], dp[j - 1]);
}
cout << rres << "\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << res[i][j];
}
cout << "\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;
cin >> t;
while (t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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...