QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288929 | #7943. LIS on Grid | ucup-team2112 | WA | 7ms | 3540kb | C++20 | 2.2kb | 2023-12-23 14:16:40 | 2023-12-23 14:16:40 |
Judging History
answer
#include <bits/stdc++.h>
void solve(){
int n, m;
std::cin >> n >> m;
std::vector<int> a(m);
for(int i = 0; i < m; i++){
std::cin >> a[i];
}
auto construct = [&](int k) {
std::vector res(n, std::vector<int>(m));
std::vector<int> b;
for (int i = 0; i < std::max(a[0], k); i += 1) {
b.emplace_back(i);
res[i][0] = 1;
}
for (int j = 1; j < m; j += 1) {
int x = std::max(k, a[j]);
for (int i = int(b.size()) - 1; i >= 0 && x; i -= 1) {
int y = b[i];
res[y][j] = 1;
y += 1;
x -= 1;
}
std::vector<int> new_b;
b.emplace_back(n);
for (int i = int(b.size()) - 2; i >= 0; i -= 1) {
int y = b[i] + 1;
while(x && y < b[i + 1]) {
res[y][j] = 1;
y += 1;
x -= 1;
}
new_b.emplace_back(y - 1);
}
std::reverse(new_b.begin(), new_b.end());
b = new_b;
}
for (int j = 0; j < m; j += 1) {
int cnt = 0;
for (int i = 0; i < n; i += 1) {
cnt += res[i][j];
}
for (int i = n - 1; i >= 0 && cnt > a[j]; i -= 1) {
if (res[i][j]) {
res[i][j] = 0;
cnt -= 1;
}
}
}
for (int i = n - 1; i >= 0; i -= 1) {
for (int j = 0; j < m; j += 1) {
std::cout << ".#"[res[i][j]];
}
std::cout << "\n";
}
};
for (int k = 0; k <= n; k += 1) {
int sum = 0;
for (int i = 0; i < m; i += 1) {
sum += std::max(0, a[i] - k);
}
if (sum <= 1ll * k * (n - k)) {
std::cout << k << "\n";
construct(k);
return;
}
}
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T;
std::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: 3540kb
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: 7ms
memory: 3508kb
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 1)