QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665816 | #7943. LIS on Grid | yanshanjiahong | WA | 9ms | 10092kb | C++14 | 1.9kb | 2024-10-22 15:26:01 | 2024-10-22 15:26:04 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)