QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#284599#7943. LIS on Griducup-team2230#WA 15ms3496kbC++173.2kb2023-12-16 14:01:122023-12-16 14:01:12

Judging History

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

  • [2023-12-16 14:01:12]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:3496kb
  • [2023-12-16 14:01:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mp make_pair
#define fr first
#define sc second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep_(_1,_2,_3,NAME,...) NAME
#define rep(...) rep_(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define rep1(i,j) for(int i=0;i<(j);i++)
#define rep2(i,j,k) for(int i=(j);i<(k);i++)

template<class T> T T_INF(){ return 1000000000000000000; }
template<> int T_INF<int>(){ return 1000000000; }

ll n,m;
ll a[200010];

bool f(int X){
    vector<int> b(n);
    for(int i=0;i<m;i++){
        int z=a[i];
        if(z>0){
            for(int j=0;j<n;j++){
                if((j==0&&b[j]>0)||(j!=0&&b[j-1]<b[j])){
                    z--;
                    if(z==0)break;
                }
            }
        }
        if(z>0){
            for(int j=n-1;j>=0;j--){
                if(((j!=0&&b[j]==b[j-1])||(j==0&&b[j]==0))&&b[j]<X){
                    z--;
                    b[j]++;
                    if(z==0)break;
                }
            }
        }
        if(z>0)return false;
    }
    return true;
}
void g(int X){
    vector<int> b(n);
    vector<string> S(n,string(m,'.'));
    for(int i=0;i<m;i++){
        int z=a[i];
        if(z>0){
            for(int j=0;j<n;j++){
                if((j==0&&b[j]>0)||(j!=0&&b[j-1]<b[j])){
                    z--;
                    S[j][i]='#';
                    if(z==0)break;
                }
            }
        }
        if(z>0){
            for(int j=n-1;j>=0;j--){
                if(((j!=0&&b[j]==b[j-1])||(j==0&&b[j]==0))&&b[j]<X){
                    z--;
                    S[j][i]='#';
                    b[j]++;
                    if(z==0)break;
                }
            }
        }
    }
    rep(i,n)cout<<S[i]<<endl;
}

void solve(){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(f(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    g(l);
}

/*void solve(){
    const int inf = 1000000000;
    vector dp(m+1,vector(n+1,inf));
    vector pre(m+1,vector(n+1,-1));
    dp[0][0]=0;
    rep(i,m){
        rep(j,n+1){
            if(dp[i][j] == inf)continue;
            if(dp[i][j] > j*n-j*(j-1)/2)continue;
            if(dp[i+1][j] > dp[i][j]+max(a[i]-j,0LL)){
                dp[i+1][j] = dp[i][j]+max(a[i]-j,0LL);
                pre[i+1][j] = j;
            }
            if(dp[i+1][j+1] > dp[i][j]+max(a[i]-j,0LL)){
                dp[i+1][j+1] = dp[i][j]+max(a[i]-j,0LL);
                pre[i+1][j+1] = j;
            }
        }
    }
    int ret=inf;
    int j_=-1;
    for(int j=n;j>=0;j--){
        if(dp[m][j] <= j*n-j*(j-1)/2){
            ret=j_=j;
        }
    }
    vector<int> js(m);
    for(int i=m;i>0;i--){
        js[i-1]=j_;
        j_=pre[i][j_];
    }
    vector<string> S(n,string(m,'.'));
    vector<int> b(n);
    rep(i,m){
        vector<int> temp;
        if(js[i]>b[n-1]){
            temp.push_back(n-1);
        }
        if(b[0]>0)temp.push_back(0);
        for(int i=1;i<n-1;i++){
            
        }
    }
    cout<<ret<<endl;
}*/

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.precision(20);
    
    int T;
    cin>>T;
    rep(t,T){
        cin>>n>>m;
        rep(i,m)cin>>a[i];
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 15ms
memory: 3488kb

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)