QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#665816#7943. LIS on GridyanshanjiahongWA 9ms10092kbC++141.9kb2024-10-22 15:26:012024-10-22 15:26:04

Judging History

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

  • [2024-10-22 15:26:04]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:10092kb
  • [2024-10-22 15:26:01]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
#define double long double
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5,M=6,S=(1<<15)+5,inf=(ll)8e18+7,mo=998244353;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int T;
int n,m,a[N];
vector<int>res[N];
int edp[N];
bool check(int k){
    rep(i,1,n){
        rep(j,1,m)
            res[i][j]=0;
    }
    rep(i,1,k)
        edp[i]=n-i+1;
    rep(i,1,m){
        rep(j,1,k)
            res[edp[j]][i]=1;
        int cnt=a[i]-k;
        if(cnt<=0)continue;
        rep(j,1,k){
            int npos=edp[j]-1;
            while(cnt&&npos&&!res[npos][i])
                cnt--,res[npos][i]=1,npos--;
            edp[j]=npos+1;
        }
        if(cnt)return 0;
    }
    rep(j,1,m){
        int cntb=0;
        rep(i,1,n){
            if(!res[i][j])continue;
            if(cntb==a[j])res[i][j]=0;
            else cntb++;
        }
    }
    return 1;
}
void solve(){
    read(n),read(m);
    rep(i,1,n){
        res[i].clear();
        rep(j,0,m)
            res[i].push_back(0);
    }
    rep(i,1,m)
        read(a[i]);
    int le=1,ri=n,ans=n;
    while(le<=ri){
        int mid=(le+ri)>>1;
        if(check(mid))ans=mid,ri=mid-1;
        else le=mid+1;
    }
    printf("%lld\n",ans);
    check(ans);
    rep(i,1,n){
        rep(j,1,m)
            printf("%c",res[i][j]?'#':'.');
        puts("");
    }
}
signed main(){
    read(T);
    while(T--)
        solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10092kb

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: 9ms
memory: 9892kb

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)