QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#285114 | #7943. LIS on Grid | ucup-team180# | WA | 6ms | 3772kb | C++17 | 1.6kb | 2023-12-16 16:35:52 | 2023-12-16 16:35:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for (int i = 0; i < t; i++){
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int j = 0; j < m; j++){
cin >> a[j];
}
int tv = n, fv = 0;
while (tv - fv > 1){
int mid = (tv + fv) / 2;
long long sum = 0;
for (int j = 0; j < m; j++){
sum += max(a[j] - mid, 0);
}
if (sum <= (long long) mid * (n - mid)){
tv = mid;
} else {
fv = mid;
}
}
int P = tv;
vector<vector<int>> cnt(P, vector<int>(m, 1));
int r = 0, s = 0;
for (int j = 0; j < m; j++){
for (int k = 0; k < max(a[j] - P, 0); k++){
if (s == n - P){
r++;
s = 0;
}
cnt[r][j]++;
s++;
}
}
for (int j = 0; j < m; j++){
int s = 0;
for (int k = 0; k < P; k++){
cnt[k][j] = min(cnt[k][j], a[j] - s);
s += cnt[k][j];
}
}
vector<int> p(m, 0);
vector<vector<char>> c(n, vector<char>(m, '.'));
for (int j = 0; j < P; j++){
for (int k = m - 1; k >= 0; k--){
if (k < m - 1){
p[k] = max(p[k], p[k + 1] - 1);
}
for (int l = 0; l < cnt[j][k]; l++){
c[p[k]][k] = '#';
p[k]++;
}
}
}
cout << P << endl;
for (int j = 0; j < n; j++){
for (int k = 0; k < m; k++){
cout << c[j][k];
}
cout << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 6ms
memory: 3772kb
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 Wrong score (test case 16)