QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300343 | #7943. LIS on Grid | jaker | RE | 0ms | 12576kb | C++14 | 2.1kb | 2024-01-08 03:44:25 | 2024-01-08 03:44:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
#define mp make_pair
#define fr first
#define se second
#define ll long long
#define MAXN 501000
#define ls (rt<<1)
#define rs (rt<<1|1)
int rd(){
int sum = 0;char c = getchar();bool flag = true;
while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}
while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();
if(!flag) sum = -sum;
return sum;
}
int n,m,k;
int a[201000],b[201000];
vector<bool>ans[201000];
void get() {
int sum = 0;
rep(i,1,m) b[i] = a[i] , sum += a[i]; sort(b+1,b+m+1);
k = 0;
int i = 0;
while( sum > 1ll*k*(n-k) ) {
while( i < n && a[i+1] <= k ) ++i;
++k; sum -= ( m - i );
}
// if( sum < 0 ) {
// printf("FUCK!\n");
// exit(0);
// }
}
int pos[201000];
void solve() {
rep(i,1,k) pos[i] = n - k + i;
int j = 1;
rep(i,1,m) {
int del = a[i] - k;
while( del > 0 ) {
if( del < pos[j] - j ) {
pos[j] -= del;
rep( t , pos[j] , pos[j] + del ) ans[t][i] = true;
del = 0;
break;
}
else {
rep( t , 1 , pos[j] ) ans[t][i] = true;
del -= ( pos[j] - j );
pos[j] = j; ++j;
}
}
// rep(t,1,k) printf("#%d ",pos[t]); printf("\n");
rep( t , 1 , k ) ans[ pos[t] ][i] = true;
}
rep(i,1,m) if( a[i] < k ) {
int del = k - a[i];
rep(j,1,n) if( del > 0 && ans[j][i] ) ans[j][i] = false , del --;
}
printf("%d\n",k);
rep(i,1,n) {
rep(j,1,m) putchar( ans[i][j] ? '#' : '.' );
putchar('\n');
}
}
void work() {
n = rd(); m = rd();
rep(i,1,n) rep(j,0,m) ans[i].pb( false );
rep(i,1,m) a[i] = rd();
get();
solve();
rep(i,1,n) ans[i].clear();
}
int main() {
int T = rd();
rep(TTT,1,T) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12576kb
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...