oj.uz

Submission #208894

# Submission time Handle Problem Language Result Execution time Memory
208894 2020-03-12T12:12:32 Z DodgeBallMan Quality Of Living (IOI10_quality) C++14
0 / 100
 65 ms 35832 KB 
#include "quality.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 3e3+5;

int sum[N][N], n, c, r, h, w;
pii pos[N*N];


bool chk( int mid, int rec[3001][3001] ) {
    memset( sum, 0, sizeof sum );
    for( int i = mid + 1 ; i <= n ; i++ ) sum[pos[i].x][pos[i].y]++;
    for( int i = 1 ; i <= r ; i++ )
        for( int j = 1 ; j <= c ; j++ )
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
    for( int i = h ; i <= r ; i++ ) 
        for( int j = w ; j <= c ; j++ ) 
            if( sum[i][j] - sum[i-h][j] - sum[i][j-w] + sum[i-h][j-w] <= h * w / 2 && pos[mid].x <= i && pos[mid].x > i-h && pos[mid].y <= j && pos[mid].y > j-w ) return true;
        
    
    return false;
}

int rectangle( int R, int C, int H, int W, int rec[3001][3001] ) {
    r = R, c = C, w = W, h = H;
    n = r*c;
	for( int i = 0 ; i < r ; i++ ) for( int j = 0 ; j < c ; j++ ) pos[rec[i][j]] = pii( i+1, j+1 );
    int l = 1, r = n;
    while( l < r ) {
        int m = l + r >> 1;
        if( chk( m, rec ) ) r = m;
        else l = m + 1;
    }
	return l;
}
/*int rrr[3001][3001];
int main()
{
    int r, c, h, w;
    scanf("%d %d %d %d",&r,&c,&h,&w);
    for( int i = 0 ; i < r ; i++ ) for( int j = 0 ; j < c ; j++ ) scanf("%d",&rrr[i][j]);
    printf("%d",rectangle( r, c, h, w, rrr ) );
}*/

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:36:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                 ~~^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -