QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300344#7943. LIS on GridjakerWA 0ms13064kbC++142.1kb2024-01-08 03:44:462024-01-08 03:44:47

Judging History

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

  • [2024-01-08 03:44:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13064kb
  • [2024-01-08 03:44:46]
  • 提交

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: 11936kb

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: 0ms
memory: 13064kb

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 number of colored cells (test case 12)