QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#285106 | #7943. LIS on Grid | ucup-team1303# | WA | 5ms | 3696kb | C++20 | 1.7kb | 2023-12-16 16:34:44 | 2023-12-16 16:34:45 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T &x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 2e5 + 10;
int n, m, a[N], f[N], t[N];
bool check(int x) {
F(i, 1, n) f[i] = 0;
int r = n;
F(i, 1, m) {
t[i] = r;
int l = r - a[i] + 1;
if (l < 1) return false;
DF(j, r, l) chkmax(f[j], f[j - 1] + 1);
while (f[r - 1] == x) r--;
}
return true;
}
void zhk() {
read(n), read(m);
bool flag = true;
F(i, 1, m) {
read(a[i]);
flag &= !a[i];
}
if (flag) {
cout << "0\n";
F(i, 1, n) {
F(j, 1, m)
cout << '.';
cout << '\n';
}
return;
}
// sort(a + 1, a + n + 1);
int l = 0, r = n;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
check(r);
// F(i, 1, m) debug << i << " " << t[i] << " " << a[i] << endl;
cout << r << '\n';
F(i, 1, n) {
F(j, 1, m) {
if (i >= t[j] - a[j] + 1 && i <= t[j]) cout << '#';
else cout << '.';
}
cout << '\n';
}
}
signed main() {
int _ = 1;
cin >> _;
while (_--) zhk();
return 0;
}
/* why?
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 5ms
memory: 3696kb
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:
4 .#..# ##..# ##.## ##.## ##### 3 ...# #..# #.## #### 2 ....# ....# ..### ##### ####. 2 .#.# .### ###. 3 .#..# .#.## .#### ##### ####. 2 #..#. #..## #..#. ####. 3 ...## ...## ##.## ##### ##### 1 ..### ..#.. ###.. #.... #.... 2 ...#. .#### .#### ###.. ###.. 2 ..... ..... ##### ##### 3 .#.#. ##.#. ###...
result:
wrong answer Jury found better answer than participant (test case 1)