QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300343#7943. LIS on GridjakerRE 0ms12576kbC++142.1kb2024-01-08 03:44:252024-01-08 03:44:27

Judging History

你现在查看的是最新测评结果

  • [2024-01-08 03:44:27]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:12576kb
  • [2024-01-08 03:44:25]
  • 提交

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;
}

详细

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...

output:


result: