QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355327 | #7943. LIS on Grid | ucup-team1198# | WA | 7ms | 9924kb | C++20 | 1.9kb | 2024-03-16 16:00:53 | 2024-03-16 16:00:53 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int MAXN = 2e5 + 100;
int a[MAXN];
string out[MAXN];
int n, m;
bool check(int k) {
vector<int> h(k, 0);
for (int i = m - 1; i >= 0; --i) {
for (int j = 0; j < n; ++j) {
out[j][i] = '.';
}
int c = a[i];
for (int j = 0; j < k && c > 0; ++j) {
if (h[j] > 0) {
--c;
out[h[j] - 1][i] = '#';
}
}
for (int j = k - 1; j >= 0; --j) {
int can_go;
if (j != 0) {
can_go = h[j - 1] - h[j] - 1;
} else {
can_go = n - h[j];
}
if (can_go <= 0) continue;
can_go = min(can_go, c);
c -= can_go;
for (int t = 0; t < can_go; ++t) {
++h[j];
out[h[j] - 1][i] = '#';
}
}
if (c > 0) return false;
}
return true;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
out[i].clear();
out[i].resize(m, '.');
}
int l = -1, r = n + 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
cout << r << "\n";
check(r);
for (int i = 0; i < n; ++i) {
cout << out[i] << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tst;
cin >> tst;
while (tst--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9844kb
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: 9924kb
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 34)