oj.uz

Submission #241876

# Submission time Handle Problem Language Result Execution time Memory
241876 2020-06-26T07:48:51 Z lakshith_ Quality Of Living (IOI10_quality) C++14
0 / 100
 7 ms 768 KB 
#include <bits/stdc++.h>
#include "quality.h"

using namespace std;

inline void io_setup(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}

void swap(int *a,int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int arr[],int lo,int hi){
  int pivot = arr[hi];
  int i = lo;
  for(int j=lo;j<hi;j++)
    if(arr[j]<=pivot)swap(&arr[i],&arr[j]),i++;
  swap(&arr[i],&arr[hi]);
  return i;
}

int randomPartition(int arr[], int l,int r){
  int n = r-l+1;
  int pivot = rand()%n;
  swap(&arr[l+pivot],&arr[r]);
  return partition(arr,l,r);
}

int median(int arr[],int l,int r,int k){
  if(k<0 || k>r-l+1)return INT_MAX;
  int pos = randomPartition(arr,l,r);
  if(pos-l==k-1)
    return arr[pos];
  if(pos-l>k-1)
    return median(arr,l,pos-1,k);
  return median(arr,pos+1,r,k-pos+l-1);
}

int rectangle(int r,int c,int h,int w,int q[3001][3001]){
  int MIN = INT_MAX;
  for(int i=0;i<r-h+1;i++)
    for(int j=0;j<c-w+1;j++){
      int arr[h*w];
      int n = 0;
      for(int k=i;k<i+h;k++)
        for(int l=j;l<j+h;l++)
          arr[n++] = q[k][l];
      MIN = min(MIN,median(arr,0,(h*w)-1,((h*w)+1)/2));
    }
  return MIN;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -