oj.uz

답안 #390726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390726 2021-04-16T19:30:49 Z Sorting 삶의 질 (IOI10_quality) C++17
100 / 100
 4313 ms 118336 KB 
#include "quality.h"
#include <bits/stdc++.h>
#pragma GCC optmize("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)
            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
*/

Compilation message

quality.cpp:3: warning: ignoring #pragma GCC optmize [-Wunknown-pragmas]
    3 | #pragma GCC optmize("O3")
      |

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 332 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 332 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 1104 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 332 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3128 KB Output is correct
8 Correct 20 ms 3228 KB Output is correct
9 Correct 21 ms 3244 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 332 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3128 KB Output is correct
8 Correct 20 ms 3228 KB Output is correct
9 Correct 21 ms 3244 KB Output is correct
10 Correct 267 ms 19044 KB Output is correct
11 Correct 230 ms 16452 KB Output is correct
12 Correct 131 ms 13656 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 332 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 20 ms 3128 KB Output is correct
8 Correct 20 ms 3228 KB Output is correct
9 Correct 21 ms 3244 KB Output is correct
10 Correct 267 ms 19044 KB Output is correct
11 Correct 230 ms 16452 KB Output is correct
12 Correct 131 ms 13656 KB Output is correct
13 Correct 4313 ms 118336 KB Output is correct
14 Correct 2794 ms 113460 KB Output is correct
15 Correct 3808 ms 111584 KB Output is correct