QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#367553 | #7943. LIS on Grid | mcpqndq | RE | 2ms | 3952kb | C++17 | 1.3kb | 2024-03-26 07:03:24 | 2024-03-26 07:03:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int tests;cin>>tests;
while(tests--){
int n,m;cin>>n>>m;
vi a(m);rep(i,0,m)cin>>a[i];
vi og=a;
vi o=a;sort(all(o));
vi ps(m+1,0);
rep(i,0,m)ps[i+1]=o[i]+ps[i];
int hi = min(n,m);
rep(k,0,min(n,m)){
int right = k*(n-k);
int i = lower_bound(all(o),k+1)-o.begin();
int left = ps.back()-ps[i]-(m-i)*k;
// cout<<k<<' '<<right<<" "<<left<<' '<<(ps.back()-ps[i])<<' '<<((m-i)*k)<<endl;
if(left<=right) hi=min(hi,k);
}
int k = hi;
cout<<k<<'\n';
vector<vector<bool>> g(n,vector<bool>(m,false));
rep(i,0,n)a[i]=max(a[i],k);
vi b=a;rep(i,0,m)b[i]-=k;
rep(i,0,k){
int y = n-k+i;
rep(x,0,m){
g[y][x]=true;
while(b[x]>0 && y>0 && !g[y-1][x]){
g[--y][x]=true;
b[x]--;
}
}
}
rep(x,0,m){
int tot = 0;
rep(y,0,n){
tot += g[y][x];
if(tot>og[x]) g[y][x]=false;
}
}
rep(i,0,n){
rep(j,0,m)cout<<(g[i][j]?'#':'.');
cout<<'\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 0
Accepted
time: 2ms
memory: 3884kb
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:
ok Correct (5699 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
1 319 626 67 228 309 13 229 146 227 223 255 224 114 146 95 37 212 200 27 113 266 302 307 5 77 213 188 115 29 22 253 296 156 237 61 19 1 69 133 304 43 125 84 54 264 124 51 107 215 277 257 74 138 123 278 42 304 83 302 155 312 41 307 56 136 290 263 92 234 164 254 247 177 44 168 176 109 34 285 9 129 269...
output:
163 ..######################################################################################################################################################################################################################################################################################################...
result:
ok Correct (1 test case)
Test #4:
score: 0
Accepted
time: 2ms
memory: 3952kb
input:
1 107 1869 7 39 65 2 18 23 35 30 85 39 102 23 66 7 21 42 69 82 84 23 9 64 75 64 9 48 12 86 31 71 51 45 70 96 100 17 12 26 53 100 60 22 54 48 85 97 59 67 107 27 73 38 41 40 71 96 14 85 29 89 30 18 42 64 14 42 98 94 105 50 54 31 41 46 105 77 4 76 87 77 75 91 71 3 106 46 101 30 63 50 86 23 68 103 98 10...
output:
96 .......................................##################################################################################################################################################################################################################################################################...
result:
ok Correct (1 test case)
Test #5:
score: 0
Accepted
time: 2ms
memory: 3904kb
input:
1 362 552 301 60 360 166 10 204 305 244 321 21 114 41 76 254 193 149 58 342 122 242 286 35 10 41 159 178 231 290 316 333 341 146 109 179 128 295 212 174 132 64 52 98 247 15 179 63 2 103 283 71 265 119 179 113 189 56 178 146 305 82 140 40 87 68 346 152 252 44 21 283 10 61 226 83 75 356 88 82 190 259 ...
output:
155 ..######################################################################################################################################################################################################################################################################################################...
result:
ok Correct (1 test case)
Test #6:
score: -100
Runtime Error
input:
1 569 351 278 304 393 23 242 475 431 408 416 63 5 240 271 175 275 328 360 429 365 456 284 434 90 356 6 518 116 367 469 495 324 267 414 481 179 67 5 222 8 238 46 112 172 295 149 92 24 261 525 244 126 77 35 558 225 484 241 401 555 139 367 284 566 344 411 377 510 49 279 246 291 208 96 561 375 272 72 27...
output:
135 ..######################################################################################################################################################################################################################################################################################################...