oj.uz

답안 #390736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390736 2021-04-16T19:48:05 Z Sorting 삶의 질 (IOI10_quality) C++17
0 / 100
 1 ms 460 KB 
#include "quality.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

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){
            if(i) a[i][j] += a[i - 1][j];
            if(j) a[i][j] += a[i][j - 1];
            if(i && j) a[i][j] -= a[i - 1][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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -