QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#573829 | #7943. LIS on Grid | NKheyuxiang | WA | 5ms | 5896kb | C++14 | 1.0kb | 2024-09-18 20:04:30 | 2024-09-18 20:04:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,a[300005];
int f[300005],pn[300005];
char mp[300005];
bool check(int k){
for(int j=1;j<=n;j++) f[j]=0;
for(int i=1;i<=m;i++){
int pos=-1;
for(int j=n;j>=1;j--){
int val=f[(i-1)*n+j];
if(pos!=-1&&pos-a[i]>=j){
f[i*n+j]=val;
continue;
}
if(j>1) val=max(val,f[(i-1)*n+j-1]+1);
else val=max(val,1);
if(pos==-1&&val<=k){
if(j<a[i]) return 0;
pos=pn[i]=j;
}
if(pos!=-1){
f[i*n+j]=val;
continue;
}
else f[i*n+j]=f[(i-1)*n+j];
}
if(pos==-1) return 0;
}
return 1;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
int l=1,r=min(n,m);
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
check(l);
printf("%d\n",l);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(pn[j]-a[j]<i&&i<=pn[j]) putchar('#');
else putchar('.');
}
puts("");
}
}
int main(){
int t;
scanf("%d",&t);
while(t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5816kb
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: 5896kb
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:
4 .#..# ##..# ##.## ##.## ##### 3 ...# #..# #.## #### 2 ....# ....# ..### ##### ####. 2 .#.# .### ###. 3 .#..# .#.## .#### ##### ####. 2 #..#. #..## #..#. ####. 3 ...## ...## ##.## ##### ##### 1 ..### ..#.. ###.. #.... #.... 2 ...#. .#### .#### ###.. ###.. 2 ..... ..... ##### ##### 3 .#.#. ##.#. ###...
result:
wrong answer Jury found better answer than participant (test case 1)