QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359304#7943. LIS on GridZanite#WA 7ms3636kbC++173.4kb2024-03-20 16:03:342024-03-20 16:03:35

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 16:03:35]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3636kb
  • [2024-03-20 16:03:34]
  • 提交

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)