Submission #390725

#	Time	Username	Problem	Language	Result	Execution time	Memory
390725		Sorting	Quality Of Living (IOI10_quality)	C++17	100 / 100	4217 ms	121476 KiB

quality

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20