QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#665275#7943. LIS on GridbilibilitdascWA 5ms9884kbC++142.0kb2024-10-22 10:42:202024-10-22 10:42:21

Judging History

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

  • [2024-10-22 10:42:21]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:9884kb
  • [2024-10-22 10:42:20]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define y0 LingLuo
#define y1 VividCycle
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using namespace std;
const ll mod1=998244353;
const ll mod2=1000000007;
unsigned time_related_rand()
{
	return unsigned(std::chrono::steady_clock::now().time_since_epoch().count());
}
int t,n,m;
int a[200005];
string s[200005];
bool check(int k)
{
	int ss=0;
	rep1(i,m) ss+=max(0,a[i]-k);
	return ss<=k*(n-k); 
}
vector<int> qt;
void Q()
{
	cin>>n>>m;
	rep1(i,m)
	{
		cin>>a[i];
	}
	int l=-1,r=n,tm;
	while(r-l>1)
	{
		tm=(l+r)>>1;
		if(check(tm)) r=tm;
		else l=tm;
	}
	++l;
	qt.clear();
	rep1(i,l) qt.pb(i);
	rep1(i,n)
	{
		s[i]="";
		rep(j,m) s[i]+='.';
	}
	rep1(i,m)
	{
		if(a[i]<=l)
		{
			rep(j,a[i]) s[qt[j]][i-1]='#';
		}
		else
		{
			a[i]-=l;
			for(int x:qt) s[x][i-1]='#';
			per(j,qt.size())
			{
				while(a[i]&&qt[i]<n&&s[qt[j]+1][i-1]=='.') s[++qt[j]][i-1]='#',--a[i];
				if(!a[i])break;
			}
		}
	}
	cout<<l<<'\n';
	per1(i,n) cout<<s[i]<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>t;while(t--)Q();return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 9880kb

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: 5ms
memory: 9884kb

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 Wrong number of colored cells (test case 1)