QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378149 | #7943. LIS on Grid | tylerm390# | WA | 6ms | 3628kb | C++20 | 1.5kb | 2024-04-06 08:09:34 | 2024-04-06 08:09:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define rep(i, a, b) for(int i = a; i < (b); i++)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
void solve() {
int n, m;
cin >> n >> m;
vi inp(m);
for (int i = 0; i < m; i++) cin >> inp[i];
int last = -1;
for (int i = 0; i < n; i++) if (inp[i] == n) last = i;
vector<string> res(n);
vi dp(n+1);
for (int i = 0; i < m; i++) {
int x = inp[i];
vi inds(n);
iota(all(inds), 0);
if (i < last) {
res[n-1].push_back('#');
x--;
inds.pop_back();
}
sort(all(inds), [&] (int u, int v) {
return make_tuple(dp[u]-dp[u+1], dp[u], -u) < make_tuple(dp[v]-dp[v+1], dp[v], -v);
});
for (int j = 0; j < x; j++) res[inds[j]].push_back('#');
for (int j = x; j < sz(inds); j++) res[inds[j]].push_back('.');
for (int i = n; i > 0; i--) {
dp[i] = max(dp[i], dp[i-1]+(res[i-1].back() == '#'));
}
for (int i = 0; i < n; i++) {
dp[i+1] = max(dp[i+1], dp[i]);
}
}
cout << dp[n] << "\n";
for (string s : res) cout << s << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 3628kb
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 Jury found better answer than participant (test case 22)