QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359219 | #7943. LIS on Grid | Zanite# | WA | 6ms | 3764kb | C++17 | 3.1kb | 2024-03-20 14:55:46 | 2024-03-20 14:55:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n, N) for (int i = (n); i <= (N); i++)
#define For(i, n, N) for (int i = (n); i < (N); i++)
#define rap(i, n, N) for (int i = (n); i >= (N); i--)
#define rip(i, n, N, V) for (int i = (n); i <= (N); i += V)
using vi = vector<int>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
using plll = pair<lll, lll>;
#define fi first
#define se second
#define ff fi.fi
#define fs fi.se
#define sf se.fi
#define ss se.se
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define endl '\n'
#define all(x) x.begin(), x.end()
#define clz(x) (1 << (31 - __builtin_clz(x)))
#define ari(x) array<int, x>
#define arll(x) array<ll, x>
#define mems(x, y) memset(x, y, sizeof x)
#define debug(x) cout << #x << " = " << (x) << endl
#define debugV(v, x) cout << #v << "[" << (x) <<> "] = " << v[x] << endl
#define out(x, y) cout << "]] " << (x) << " " << (y) << endl
#ifdef LOCAL
#define DEBUG(...) __VA_ARGS__;
#else
#define DEBUG(...)
#endif
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
return os << "(" << p.fi << ", " << p.se << "\n";
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
os << "{"; bool osu = 1;
for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
return os << "}";
}
template<class T, ull sz>
ostream& operator<<(ostream& os, const array<T, sz> &v) {
os << "{"; bool osu = 1;
for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
return os << "}";
}
void solve(int tt = -1) {
DEBUG(cerr << "tt = " << tt << '\n');
int n, m; cin >> n >> m;
vi a(m);
for(int &i : a) cin >> i;
vector<vi> grid(n, vi(m));
const auto check = [&](int x) {
For(i, 0, n) For(j, 0, m) grid[i][j] = 0;
vi val(n), nval(n);
For(j, 0, m) {
int mx = 0;
rep(i, 0, n-1) {
nval[i] = mx+1;
mx = max(mx, val[i]);
}
int mn = -1;
rap(i, n-1, 0) {
if(nval[i] <= x) {
mn = i;
break;
}
}
if(mn == -1) return false;
For(i, 0, a[j]) {
if(mn-i < 0) return false;
grid[mn-i][j] = 1;
val[mn-i] = nval[mn-i];
}
}
return true;
};
int l = 1, r = n, ans = -1;
while(l <= r) {
int mid = (l+r)/2;
if(check(mid))
ans = mid, r = mid-1;
else
l = mid+1;
}
check(ans);
cout << ans << '\n';
For(i, 0, n) For(j, 0, m) {
cout << (grid[i][j] ? '#' : '.');
if(j+1==m) cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
rep(tc, 1, t) solve(tc);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
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: 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:
4 .#..# ##..# ##.## ##.## ##### 3 ...# #..# #.## #### 2 ....# ....# ..### ##### ####. 2 .#.# .### ###. 3 .#..# .#.## .#### ##### ####. 2 #..#. #..## #..#. ####. 3 ...## ...## ##.## ##### ##### 1 ..### ..#.. ###.. #.... #.... 2 ...#. .#### .#### ###.. ###.. 2 ..... ..... ##### ##### 3 .#.#. ##.#. ###...
result:
wrong answer Jury found better answer than participant (test case 1)