QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#284838#7943. LIS on Griducup_team_qiuly#WA 7ms8540kbC++17755b2023-12-16 15:13:262023-12-16 15:13:27

Judging History

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

  • [2023-12-16 15:13:27]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:8540kb
  • [2023-12-16 15:13:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int T,n,m,l,r,ans,a[N],w[N];vector<int> z[N];
bool chk(int x)
{
	fill(w+1,w+m+1,0);
	for(int i=1,t;i<=n;++i)
	{
		fill(z[i].begin(),z[i].end(),0);t=a[i];
		for(int j=1;j<=m && t;++j) if(w[j]>w[j-1]) --t,z[i][j]=1;
		for(int j=m;j && t;--j) if(w[j]<x && w[j]==w[j-1])
			--t,++w[j],z[i][j]=1;if(t) return 0;
	}return 1;
}
void slv()
{
	scanf("%d %d",&m,&n);l=1;r=m;
	for(int i=1;i<=n;++i) z[i].resize(m+1),scanf("%d",&a[i]);
	while(l<=r) {int mid=(l+r)/2;if(chk(mid)) r=mid-1;else l=mid+1;}
	printf("%d\n",l);chk(l);
	for(int i=1;i<=m;++i,putchar('\n'))
		for(int j=1;j<=n;++j) putchar(z[j][i]?'#':'.');
}
int main()
{
	scanf("%d",&T);
	while(T--) slv();return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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)