oj.uz

답안 #390725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390725 2021-04-16T19:30:01 Z Sorting 삶의 질 (IOI10_quality) C++17
100 / 100
 4217 ms 121476 KB 
#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 3000 + 3;

int *q[N];
int r, c, h, w, sr, sc;
pair<int, int> p[N * N];
int a[N][N];

void update(int x1, int y1, int x2, int y2){
    a[x1][y1]++;
    a[x1][y2 + 1]--;
    a[x2 + 1][y1]--;
    a[x2 + 1][y2 + 1]++;
}

bool check(int mid){
    for(int i = 1; i <= mid; ++i){
        auto [x, y] = p[i];
        update(max(x - h + 1, 0), max(y - w + 1, 0), min(x, r - h), min(y, c - w));
    }

    for(int i = 1; i < sr; ++i)
        for(int j = 0; j < sc; ++j)
            a[i][j] += a[i - 1][j];
    for(int i = 0; i < sr; ++i)
        for(int j = 1; j < sc; ++j)
            a[i][j] += a[i][j - 1];

    int mx = 0;
    for(int i = 0; i < sr; ++i)
        for(int j = 0; j < sc; ++j){
            mx = max(mx, a[i][j]);
            a[i][j] = 0;
       }
    return mx >= (h * w / 2 + 1);
}

int rectangle(int _r, int _c, int _h, int _w, int _q[3001][3001]) {
    r = _r, c = _c, h = _h, w = _w;
    for(int i = 0; i < r; ++i)
        q[i] = _q[i];

    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j)
            p[q[i][j]] = {i, j};

    sr = r - h + 1;
    sc = c - w + 1;

    int l_bs = 1, r_bs = r * c;
    while(l_bs != r_bs){
        int mid = (l_bs + r_bs) >> 1;
        if(check(mid)) r_bs = mid;
        else l_bs = mid + 1;
    }
    return l_bs;
}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 428 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3660 KB Output is correct
8 Correct 20 ms 3648 KB Output is correct
9 Correct 20 ms 3692 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3660 KB Output is correct
8 Correct 20 ms 3648 KB Output is correct
9 Correct 20 ms 3692 KB Output is correct
10 Correct 262 ms 21936 KB Output is correct
11 Correct 233 ms 19372 KB Output is correct
12 Correct 135 ms 16664 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3660 KB Output is correct
8 Correct 20 ms 3648 KB Output is correct
9 Correct 20 ms 3692 KB Output is correct
10 Correct 262 ms 21936 KB Output is correct
11 Correct 233 ms 19372 KB Output is correct
12 Correct 135 ms 16664 KB Output is correct
13 Correct 4217 ms 121476 KB Output is correct
14 Correct 2772 ms 116572 KB Output is correct
15 Correct 3895 ms 114804 KB Output is correct