QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290796 | #7943. LIS on Grid | ucup-team902# | WA | 10ms | 3728kb | C++20 | 2.5kb | 2023-12-25 15:28:28 | 2023-12-25 15:28:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define gc c=getchar()
#define r(x) read(x)
#define ll long long
template<typename T>
inline void read(T &x){
x=0;T k=1;char gc;
while(!isdigit(c)){if(c=='-')k=-1;gc;}
while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}
inline bool check(int x, int n, int m, vector<int> &a){
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
vector<vector<int>> sufmax(n + 1, vector<int>(m + 1, 0));
for(int j = m - 1; ~j; --j){
int res = a[j];
for(int i = 0; i < n; ++i){
if(res && sufmax[i + 1][j + 1] + 1 <= x){
dp[i][j] = sufmax[i + 1][j + 1] + 1;
--res;
}
else{
dp[i][j] = sufmax[i + 1][j + 1];
}
}
if(res) return false;
for(int i = n - 1; ~i; --i){
sufmax[i][j] = max(sufmax[i + 1][j], dp[i][j]);
}
}
return true;
}
inline void output(int x, int n, int m, vector<int> &a){
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
vector<vector<char>> ans(n, vector<char>(m));
vector<vector<int>> sufmax(n + 1, vector<int>(m + 1, 0));
for(int j = m - 1; ~j; --j){
int res = a[j];
for(int i = 0; i < n; ++i){
if(res && sufmax[i + 1][j + 1] + 1 <= x){
dp[i][j] = sufmax[i + 1][j + 1] + 1;
--res;
ans[i][j] = '#';
}
else{
dp[i][j] = sufmax[i + 1][j + 1];
ans[i][j] = '.';
}
}
if(res) return assert(0);
for(int i = n - 1; ~i; --i){
sufmax[i][j] = max(sufmax[i + 1][j], dp[i][j]);
}
}
printf("%d\n", x);
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
putchar(ans[i][j]);
}
putchar('\n');
}
}
void solve(){
int n, m; r(n), r(m);
vector<int> a;
for(int i = 0; i < m; ++i){
int x; r(x);
a.push_back(x);
}
int l = 0, r = min(n, m), ans;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid, n, m, a)){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
output(ans, n, m, a);
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T; r(T);
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
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: 10ms
memory: 3728kb
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 #### .### .#.. 4 ##### ##### .#### .#.## .#... 2 ##### #..#. #..#. #..#. 3 ..### ##### ##.## ##.## ...## 1 ..### ..#.. ###.. #.... #.... 2 ..### .#### ####. ###.. .#... 2 ##### ##### ..... ..... 3 .#### ####. ###...
result:
wrong answer Wrong score (test case 1)