oj.uz

Submission #295635

# Submission time Handle Problem Language Result Execution time Memory
295635 2020-09-09T19:23:44 Z mat_v Quality Of Living (IOI10_quality) C++14
0 / 100
 1 ms 768 KB 
//#include "quality.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m,h,w;

int mat[3005][3005];
int pref[3005][3005][2];

int get(int a, int b, int c, int d, int idx){
    int ans = 0;
    ans += pref[c][d][idx];
    ans += pref[a - 1][b - 1][idx];
    ans -= pref[a - 1][d][idx];
    ans -= pref[c][b - 1][idx];
    return ans;
}


bool check(int x){
    ff(i,1,n){
        ff(j,1,m){
            ff(k,0,1)pref[i][j][k] = pref[i - 1][j][k] + pref[i][j - 1][k] - pref[i - 1][j - 1][k];
            if(mat[i][j] < x)pref[i][j][0]++;
            else if(mat[i][j] > x)pref[i][j][1]++;
        }
    }
    ff(i,1,n - h + 1){
        ff(j,1,m - w + 1){
            ff(k,0,1){
                int sta = get(i,j,i+h,j+w,k);
                int kol = n*w;
                if(sta > (kol + 1)/2)return 0;
            }
        }
    }
    return 1;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    n = R;
    m = C;
    h = H;
    w = W;
    ff(i,0,n - 1){
        ff(j,0,m - 1){
            mat[i + 1][j + 1] = Q[i][j];
        }
    }
    int l = 1;
    int r = n*m;
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid)){
            r = mid;
        }
        else l = mid + 1;
    }
    return l;
}

Compilation message

quality.cpp: In function 'bool check(int)':
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:41:5: note: in expansion of macro 'ff'
   41 |     ff(i,1,n){
      |     ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:42:9: note: in expansion of macro 'ff'
   42 |         ff(j,1,m){
      |         ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:43:13: note: in expansion of macro 'ff'
   43 |             ff(k,0,1)pref[i][j][k] = pref[i - 1][j][k] + pref[i][j - 1][k] - pref[i - 1][j - 1][k];
      |             ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:48:5: note: in expansion of macro 'ff'
   48 |     ff(i,1,n - h + 1){
      |     ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:49:9: note: in expansion of macro 'ff'
   49 |         ff(j,1,m - w + 1){
      |         ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:50:13: note: in expansion of macro 'ff'
   50 |             ff(k,0,1){
      |             ^~
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:65:5: note: in expansion of macro 'ff'
   65 |     ff(i,0,n - 1){
      |     ^~
quality.cpp:8:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
quality.cpp:66:9: note: in expansion of macro 'ff'
   66 |         ff(j,0,m - 1){
      |         ^~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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