QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359304 | #7943. LIS on Grid | Zanite# | WA | 7ms | 3636kb | C++17 | 3.4kb | 2024-03-20 16:03:34 | 2024-03-20 16:03:35 |
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;
int cur = 0;
rep(i, 0, n-1) {
if(val[i] == nval[i]) cur++;
else cur = 0;
if(cur == a[j]) {
mn = i;
break;
}
}
if(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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
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: 3560kb
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)