QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760573#7943. LIS on GridCapitanWA 7ms5776kbC++204.0kb2024-11-18 17:39:142024-11-18 17:39:15

Judging History

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

  • [2024-11-18 17:39:15]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:5776kb
  • [2024-11-18 17:39:14]
  • 提交

answer

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define md(x)         (((x%MD)+MD)%MD)
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;
int n,m;
int arr[N];
vector<char> ans[N];
vector<int> dp[N],dp2[N];
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m ;
        for(int i =1;i<=m;i++) cin >> arr[i];
        for(int i = 0;i<=n;i++){
            ans[i].clear();
            dp[i].clear();
            dp2[i].clear();
            for(int j = 1;j<=m+1;j++) ans[i].pb('.');
            for(int j =1;j<=m+1;j++) dp[i].pb(n+1);
            for(int j =1;j<=m+1;j++) dp2[i].pb(0);
        }
        dp[1][1] = n - arr[1] + 1;
        for(int j = 2;j<=m;j++){
            int l = n - arr[j] + 1;
            int r = n;
            for(int i = 1;i<=n;i++){
                if(dp[i-1][j-1] < n) dp[i][j] = max(dp[i-1][j-1] + 1,l);
            }
            for(int i = 0;i<=n;i++) dp[i][j] = min(dp[i][j],dp[i][j-1]);
            dp[1][j] = min(dp[1][j],l);
        }
        dp2[1][m] = arr[m];
        for(int j = m-1;j>=1;j--){
            int l = 1;
            int r = arr[j];
            for(int i = 1;i<=n;i++){
                if(dp2[i-1][j+1] > 1){
                    dp2[i][j] = max(0,min(dp2[i-1][j+1] - 1,r));
                }
            }
            for(int i = 0;i<=n;i++) dp2[i][j] = max(dp2[i][j],dp2[i][j+1]);
            dp2[1][j] = max(dp2[1][j],arr[j]);
        }
        //cout << "--" << endl;
        //for(int i = 1;i<=n;i++){
        //    for(int j = 1;j<=m;j++) cout << dp[i][j] << sep;
        //    cout << endl;
        //}
        //cout << "--" << endl;
        //for(int i = 1;i<=n;i++){
        //    for(int j = 1;j<=m;j++){
        //        cout << dp2[i][j] << sep;
        //    }
        //    cout << endl;
        //}
        pii lis = Mp(0,m);
        for(int i = 1;i<=n;i++){
            if(dp[i][m] <= n) lis.fi = max(lis.fi,i);
        }
        for(int j = 0;j<m;j++){
            int tmp = 0;
            for(int i = 1;i<=n;i++){
                if(dp2[i][j+1]){
                    int dw = 0,up=n+1;
                    while(up-dw>1){
                        int mid = (up+dw)>>1;
                        if(dp[mid][j] < dp2[i][j+1]) dw = mid;
                        else up = mid;
                    }
                    tmp = max(tmp,i+dw);
                }
            }
            for(int i = 1;i<=n;i++){
                if(dp2[i][j+1]) tmp = max(tmp,i);
                if(dp[i][j] <= n) tmp = max(tmp,i);
            }
            lis = min(lis,Mp(tmp,j));
        }
        cout << lis.fi << endl;
        for(int j = 1;j<=lis.sec;j++){
            for(int i = n-arr[j]+1;i<=n;i++) ans[i][j] = '#';
        }
        for(int j = lis.sec+1;j<=m;j++){
            for(int i = 1;i<=arr[j];i++) ans[i][j] = '#';
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++) cout << ans[i][j];
            cout << endl;
        }
        
       
        
        
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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

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

result:

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