QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#514327#7943. LIS on GridSwarthmore#WA 5ms3832kbC++201.9kb2024-08-11 00:37:032024-08-11 00:37:04

Judging History

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

  • [2024-08-11 00:37:04]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3832kb
  • [2024-08-11 00:37:03]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const char nl = '\n';

int N, M;
vi A;

vector<string> ans;

bool ok(int K) {
    int val[N+1]; F0R(i, N+1) val[i] = 0;
    F0R(i, N) F0R(j, M) ans[i][j] = '.';
    F0R(j, M) {
        int cur = A[j];
        F0Rd(i, N) {
            if (cur && val[i+1] >= val[i]+1) {
                ans[i][j] = '#';
                cur--;
            }
        }
        F0Rd(i, N) {
            if (cur && val[i] < K && ans[i][j] == '.') {
                ans[i][j] = '#';
                val[i+1] = max(val[i+1], val[i]+1);
                cur--;
            }
        }
        FOR(i, 1, N+1) val[i] = max(val[i], val[i-1]);
        if (cur) return false;
    }
    return true;
}


void solve() {
    cin >> N >> M;
    A = vi(M);
    F0R(i, M) cin >> A[i];
    string S;
    F0R(i, M) {
        S += '.';
    }
    ans.clear();
    F0R(i, N) ans.pb(S);

    int lo = 1, hi = min(N, M);
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(mid)) {
            hi = mid;
        } else lo = mid+1;
    }
    cout << lo << nl;
    ok(lo);

    F0R(i, N) {
        F0R(j, M) {
            cout << ans[i][j];
        }
        cout << nl;
    }
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
	while (T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

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: 3832kb

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
.###.
##...
###...

result:

wrong answer Jury found better answer than participant (test case 21)