oj.uz

답안 #241878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241878 2020-06-26T07:58:08 Z lakshith_ 삶의 질 (IOI10_quality) C++14
40 / 100
 5000 ms 2432 KB 
#include <bits/stdc++.h>
#include "quality.h"

using namespace std;


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+w;l++)
          arr[n++] = q[k][l];
      MIN = min(MIN,median(arr,0,(h*w)-1,((h*w)+1)/2));
    }
  return MIN;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 78 ms 768 KB Output is correct
5 Correct 74 ms 768 KB Output is correct
6 Correct 44 ms 768 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 78 ms 768 KB Output is correct
5 Correct 74 ms 768 KB Output is correct
6 Correct 44 ms 768 KB Output is correct
7 Execution timed out 5050 ms 2432 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 78 ms 768 KB Output is correct
5 Correct 74 ms 768 KB Output is correct
6 Correct 44 ms 768 KB Output is correct
7 Execution timed out 5050 ms 2432 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 78 ms 768 KB Output is correct
5 Correct 74 ms 768 KB Output is correct
6 Correct 44 ms 768 KB Output is correct
7 Execution timed out 5050 ms 2432 KB Time limit exceeded
8 Halted 0 ms 0 KB -