oj.uz

Submission #314479

# Submission time Handle Problem Language Result Execution time Memory
314479 2020-10-20T03:22:39 Z VROOM_VARUN Quality Of Living (IOI10_quality) C++14
100 / 100
 3409 ms 176180 KB 
/*
ID: varunra2
LANG: C++
TASK: quality
*/

#include<bits/stdc++.h>
#include "quality.h"
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

const int MAXN = 3003;

VVI pref(MAXN, VI(MAXN));
VVI vals(MAXN, VI(MAXN, INF));
int h, w, r, c;

void clr() {
  trav(x, pref) {
    trav(y, x) y = 0;
  }
}

void genPref() {
  for(int i = 0; i < MAXN; i++) {
    for(int j = 0; j < MAXN; j++) {
      if(i) pref[i][j] += pref[i - 1][j];
      if(j) pref[i][j] += pref[i][j - 1];
      if(i and j) pref[i][j] -= pref[i - 1][j - 1];
    }
  }
}

int qry(int a, int b, int c, int d) {
  int ret = pref[c][d];
  if(a) ret -= pref[a - 1][d];
  if(b) ret -= pref[c][b - 1];
  if(a and b) ret += pref[a - 1][b - 1];
  return ret;
}

int qry(int i, int j) {
  return qry(i - h + 1, j - w + 1, i, j);
}

void gen(int x) {
  rep(i, 0, MAXN) rep(j, 0, MAXN) pref[i][j] = (bool)(vals[i][j] <= x);
  genPref();
}

bool works(int x) {
  gen(x);
  rep(i, h - 1, MAXN) rep(j, w - 1, MAXN) {
    if(qry(i, j) * 2 > h * w) return true;
  }
  return false;
}

int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
  rep(i, 0, r) rep(j, 0, c) vals[i][j] = --q[i][j];
  ::r = r;
  ::c = c;
  ::h = h;
  ::w = w;
  int x = -1;
  int z = r * c;
  for(int b = z + 1; b >= 1; b /= 2) {
    while(!(works(x + b))) x += b;
  }
  return x + 2;
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("quality.in", "r", stdin);
//   freopen("quality.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0); cin.tie(0);

//   int qq;
//   cin >> qq;

//   while(qq--) {
//     int h, w, r, c;
//     cin >> h >> w >> r >> c;
//     int q[r][c];
//     for(int i = 0; i < r; i++) {
//       for(int j = 0; j < c; j++) {
//         cin >> q[i][j];
//       }
//     }
//     debug(rectangle(h, w, r, c, q));
//   }

//   return 0;
// }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 71288 KB Output is correct
2 Correct 950 ms 71416 KB Output is correct
3 Correct 614 ms 71352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 71288 KB Output is correct
2 Correct 950 ms 71416 KB Output is correct
3 Correct 614 ms 71352 KB Output is correct
4 Correct 1240 ms 71708 KB Output is correct
5 Correct 1180 ms 71800 KB Output is correct
6 Correct 1320 ms 71800 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 71288 KB Output is correct
2 Correct 950 ms 71416 KB Output is correct
3 Correct 614 ms 71352 KB Output is correct
4 Correct 1240 ms 71708 KB Output is correct
5 Correct 1180 ms 71800 KB Output is correct
6 Correct 1320 ms 71800 KB Output is correct
7 Correct 1453 ms 73208 KB Output is correct
8 Correct 1656 ms 73336 KB Output is correct
9 Correct 1444 ms 73208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 71288 KB Output is correct
2 Correct 950 ms 71416 KB Output is correct
3 Correct 614 ms 71352 KB Output is correct
4 Correct 1240 ms 71708 KB Output is correct
5 Correct 1180 ms 71800 KB Output is correct
6 Correct 1320 ms 71800 KB Output is correct
7 Correct 1453 ms 73208 KB Output is correct
8 Correct 1656 ms 73336 KB Output is correct
9 Correct 1444 ms 73208 KB Output is correct
10 Correct 1815 ms 85988 KB Output is correct
11 Correct 1925 ms 86008 KB Output is correct
12 Correct 1838 ms 80516 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 71288 KB Output is correct
2 Correct 950 ms 71416 KB Output is correct
3 Correct 614 ms 71352 KB Output is correct
4 Correct 1240 ms 71708 KB Output is correct
5 Correct 1180 ms 71800 KB Output is correct
6 Correct 1320 ms 71800 KB Output is correct
7 Correct 1453 ms 73208 KB Output is correct
8 Correct 1656 ms 73336 KB Output is correct
9 Correct 1444 ms 73208 KB Output is correct
10 Correct 1815 ms 85988 KB Output is correct
11 Correct 1925 ms 86008 KB Output is correct
12 Correct 1838 ms 80516 KB Output is correct
13 Correct 3409 ms 133860 KB Output is correct
14 Correct 3089 ms 176180 KB Output is correct
15 Correct 3307 ms 168712 KB Output is correct