제출 #976483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976483		LaviniaTornaghi	삶의 질 (IOI10_quality)	C++14	40 / 100	5032 ms	6748 KiB

quality

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

void print(multiset<int> x){
	for(auto i:x) cout<<i<<" ";
	cout<<endl;
}

int A,B;

void addcolumn(vector<vector<int>> &q, multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++) s.insert(q[i][c]);
}
void removecolumn(vector<vector<int>> &q,multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[i][c]));
	}
}
void addrow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++) s.insert(q[r][i]);
}
void removerow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[r][i]));
	}
}
int getmed(multiset<int>&s){
	int l = *(s.begin()), r = *(s.rbegin());
	while(r-l>1){
		int m = (l+r)/2;
		if( distance(s.begin(),s.lower_bound(m)) >(s.size()/2)) r = m;
		else l = m;
	}
	return l;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> q(R,vector<int>(C)); A=R, B=C;
	for(int i=0;i<R;i++)
		for(int j=0;j<C;j++)
			q[i][j]=Q[i][j];
	
	multiset<int> s;
	int ans = INT_MAX;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			s.insert(q[i][j]);
	for(int i=0;i<=R-H;i++){
		if(!(i%2)){
			for(int j=1;j<=C-W;j++){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j-1,i,i+H);
				addcolumn(q,s,j+W-1,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,C-W,C);
			if(i+H<R)addrow(q,s,i+H,C-W,C);
		}else{
			for(int j=C-W-1;j>=0;j--){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j+W,i,i+H);
				addcolumn(q,s,j,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,0,W);
			if(i+H<R) addrow(q,s,i+H,0,W);
		}
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

quality.cpp: In function 'int getmed(std::multiset<int>&)':
quality.cpp:36:44: warning: comparison of integer expressions of different signedness: 'std::__iterator_traits<std::_Rb_tree_const_iterator<int>, void>::difference_type' {aka 'long int'} and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if( distance(s.begin(),s.lower_bound(m)) >(s.size()/2)) r = m;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20