oj.uz

Submission #390738

# Submission time Handle Problem Language Result Execution time Memory
390738 2021-04-16T19:50:55 Z Sorting Quality Of Living (IOI10_quality) C++17
100 / 100
 4495 ms 118296 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 = 0; 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
20.0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 2 ms 972 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

# Verdict Execution time Memory 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 2 ms 972 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 24 ms 3108 KB Output is correct
8 Correct 19 ms 3224 KB Output is correct
9 Correct 23 ms 3268 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory 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 2 ms 972 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 24 ms 3108 KB Output is correct
8 Correct 19 ms 3224 KB Output is correct
9 Correct 23 ms 3268 KB Output is correct
10 Correct 256 ms 19044 KB Output is correct
11 Correct 218 ms 16432 KB Output is correct
12 Correct 129 ms 13648 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory 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 2 ms 972 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 24 ms 3108 KB Output is correct
8 Correct 19 ms 3224 KB Output is correct
9 Correct 23 ms 3268 KB Output is correct
10 Correct 256 ms 19044 KB Output is correct
11 Correct 218 ms 16432 KB Output is correct
12 Correct 129 ms 13648 KB Output is correct
13 Correct 4495 ms 118296 KB Output is correct
14 Correct 2878 ms 113460 KB Output is correct
15 Correct 3785 ms 111640 KB Output is correct