QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288552#7943. LIS on GridWRuperDRE 0ms19992kbC++141.8kb2023-12-22 21:37:182023-12-22 21:37:19

Judging History

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

  • [2023-12-22 21:37:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:19992kb
  • [2023-12-22 21:37:18]
  • 提交

answer

// Problem:  LIS on Grid
// Contest: Virtual Judge - QOJ
// URL: https://vjudge.csgrandeur.cn/problem/QOJ-7943
// Memory Limit: 253 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 3e5 + 10;
int a[MAX];
map <int, int> mp[MAX];
int b[MAX];

void solve(){
	int n = read(), m = read();
	for(int i = 1; i <= m; i++){
		a[i] = read();
	}
	int l = 0, r = m;
	while(l <= r){
		int mid = (l + r) >> 1;	
		int cnt = 0;
		for(int i = 1; i <= m; i++){
			b[i] = a[i] - mid;
			b[i] = max(0ll, b[i]);
			cnt += b[i];
		}
		if(cnt > (n - mid) * mid){
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	write(l), endl;
	int k = l;
	for(int i = 1; i <= m; i++){
		b[i] = a[i] - k;
		b[i] = max(0ll, b[i]);
	}
	for(int i = n - k + 1; i <= n; i++){
		int now = 1;
		int nowy = i;
		int cnt = n - k;
		while(now <= m){
			mp[nowy][now] = 1;
			while(b[now] and cnt){
				cnt--, b[now]--;
				nowy--;
				mp[nowy][now] = 1;
			}
			now++;
		}
		now = m;
		while(nowy > (i - (n - k + 1) + 1)){
			nowy--;
			mp[nowy][now] = 1;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(mp[i][j] and a[j])	putchar('#'), a[j]--;
			else putchar('.');
		}endl;
	}
	for(int i = 1; i <= n; i++){
		mp[i].clear();
	}
}

signed main(){
	int t = read();
	while(t--)	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: