QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288552 | #7943. LIS on Grid | WRuperD | RE | 0ms | 19992kb | C++14 | 1.8kb | 2023-12-22 21:37:18 | 2023-12-22 21:37:19 |
Judging History
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...