QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#295103 | #7943. LIS on Grid | ckiseki | WA | 10ms | 3760kb | C++20 | 2.6kb | 2023-12-30 18:58:48 | 2023-12-30 18:58:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define orange(...) safe
#define debug(...) safe
#endif
using lld = int64_t;
bool out = true;
bool fu;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; i++) {
cin >> a[i];
}
if (fu)
{
cout << n << ' ' << m << '\n';
for (int i = 0; i < m; i++) {
cout << a[i] << '\n';
}
}
auto ans = vector(n, vector(m, 0));
ans[0][0] = 1;
const auto valid = [&](int value, bool construct = false) {
vector<int> v(value, 1);
for (int k = 0; k < m; k++) {
int distinct = v.size();
for (size_t i = 1; i < v.size(); i++)
distinct -= v[i] == v[i - 1];
int left = max(0, a[k] - distinct);
vector<int> nv(value);
for (int i = 0; i < value; i++) {
int d = max(0, i ? v[i - 1] - v[i] - 1 : n + 1 - v[i] - 1);
nv[i] = v[i] + min(left, d);
left -= min(left, d);
}
if (left) {
return false;
}
if (construct) {
for (int i = 0; i < value; i++) {
for (int j = v[i]; j <= nv[i]; j++) {
ans[j - 1][k] = 1;
}
}
}
v = nv;
}
return true;
};
int l = 0, r = n;
while (r - l > 1) {
int m = (l + r) / 2;
if (valid(m)) {
r = m;
} else {
l = m;
}
}
valid(r, true);
cout << r << '\n';
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (ans[i][j]) {
a[j]--;
if (a[j] < 0) ans[i][j] = 0;
}
}
}
if (out)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << ".#"[ans[n - 1 - i][j]];
}
cout << '\n';
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
if (T >= 196) out = false;
int cnt = 0;
while (T--)
{
++cnt;
if (cnt == 196) out = fu = true;
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 10ms
memory: 3760kb
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 3 1 2 3 2 2 2 3 2 3 2 2 3 2 2 2 2 2 2 2 2 4 2 2 3 2 1 1 3 1 2 2 2 2 2 2 2 2 3 3 3 2 1 2 2 2 2 2 2 2 2 3 2 1 2 2 2 3 1 2 3 3 3 3 3 1 1 1 3 3 2 2 3 2 2 3 3 2 2 2 3 2 3 2 3 2 2 2 2 2 2 2 3 1 2 3 4 3 3 3 3 3 2 3 2 2 2 2 3 1 3 3 3 2 2 2 2 2 2 2 4 2 3 3 2 2 2 2 3 3 1 3 2 3 1 3 2 2 2 ...
result:
wrong answer Token parameter [name=s] equals to "2", doesn't correspond to pattern "[.#]{5,5}" (test case 1)