QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355752#7943. LIS on GridVladMWA 16ms3608kbC++141.6kb2024-03-17 05:41:482024-03-17 05:41:49

Judging History

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

  • [2024-03-17 05:41:49]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3608kb
  • [2024-03-17 05:41:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define DIM 200007

int n, m, a[DIM], pos[DIM], mn[DIM];

set<pair<int, int> > s;

bool cando(int k){
    s.clear();
    for(int i = 1; i <= k; ++i) {pos[i] = n; mn[i] = n - a[i] + 1; s.insert({i - mn[i], -i});}
    int currmax = n;
    for(int i = k + 1; i <= m; ++i){
        pos[i] = min(k - (*s.begin()).first, currmax);
        //if(k == 2) cout << i << ' ' << pos[i] << endl;
        if(pos[i] - a[i] + 1 < 1) return false;
        mn[i] = pos[i] - a[i] + 1;
        currmax = pos[i];
        pair<int, int> p = *s.begin();
        //cout << p.first << ' ' << p.second << endl;
        s.erase(p);
        vector<pair<int, int> > need_to_del;
        for(auto P : s){
            int id = -P.second;
            if(id > -p.second) need_to_del.push_back(P);
        }
        for(auto P : need_to_del){
            s.erase(P);
            s.insert({P.first - 1, P.second});
        }
        s.insert({k - mn[i], -i});
    }
    return true;
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) cin >> a[i];
    int l = 1;
    int r = min(n, m);
    while(l < r){
        int m = (l + r) >> 1;
        if(cando(m)) r = m;
        else l = m + 1;
    }
    cout << l << endl;
    cando(l);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(i < mn[j] || i > pos[j]) cout << '.';
            else cout << '#';
        }
        cout << endl;
    }
    return;
}

int main()
{
    int t = 0;
    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: 3540kb

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: 16ms
memory: 3608kb

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)