oj.uz

답안 #232419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232419 2020-05-17T00:51:31 Z crossing0ver 삶의 질 (IOI10_quality) C++17
60 / 100
 5000 ms 23160 KB 
#include<bits/stdc++.h>
#include "quality.h"
using namespace std;
const int N = 9E5 + 5;
int median;

int t[4*N];
int pos,numb,ans = INT_MAX;
void upd (int v = 1,int tl = 1,int tr = numb) {
	if (tl == tr) {
		if (t[v]) t[v] = 0;
		else t[v] = 1;
		return;
	}
	int tm = (tl +tr)/2;
	if (pos <= tm)
		upd (v*2,tl,tm);
	else upd (v*2|1,tm+1,tr);
	t[v] = t[v*2] + t[v*2 + 1];
}
int get (int v = 1, int tl = 1, int tr = numb,int F = median) {
	if (tl == tr) return tl;
	int tm = (tl + tr)/2;
//	if (F <= t[v*2+1]) return get(v*2 + 1,tm + 1,tr,F);
	
//	F -= t[v*2 + 1];
//	return get(v*2,tl,tm,F);    
	if (F <= t[v*2]) return get(v*2,tl,tm,F);
	F -= t[v*2];
	return get(v*2|1,tm+1,tr,F);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	numb = R*C;
	median = (H*W+1)/2;
	for (int i = 0; i < H; i++)
	for (int j = 0; j < W; j++) {
		pos = Q[i][j];
		upd();
	}
//	ans = get();
//	cout << ans;
//	exit(0);
	int r = W - 1, l = 0, h = 0, d = H - 1;
	int dir = 0; // 0 - r  1 - d   2 - l
	while (true) {
		ans = min(ans,get());
		if (dir == 0) {
			if (r != C - 1) {
				for (int i = h; i <= d; i++) {
					pos = Q[i][l];
					upd();
					pos = Q[i][r + 1];
					upd();
				}
				r++;
				l++;																		
			}
			else if (d != R - 1){
				dir = 1;
				for (int i = l; i <=r ; i++) {
					pos = Q[h][i];
					upd();
					pos = Q[d + 1][i];
					upd();
				}
				h++;
				d++;
			}
			else break;
		}
		else	if (dir == 1) {
				if (l != 0) {
					dir = 2;
					for (int i = h; i <= d; i++) {
					pos = Q[i][r];
					upd();
					pos = Q[i][l-1];
					upd();
				}
				r--;
				l--;
			}
			else if (r != C - 1) {
				dir = 0;
				for (int i = h; i <= d; i++) {
					pos = Q[i][l];
					upd();
					pos = Q[i][r + 1];
					upd();
				}
				r++;
				l++;
			}
			else if (d != R - 1) {
				for (int i = l; i <=r ; i++) {
					pos = Q[h][i];
					upd();
					pos = Q[d + 1][i];
					upd();
				}
				h++;
				d++;
			}
			else break;
			}
			else {
				if (l != 0) {
					for (int i = h; i <= d; i++) {
					pos = Q[i][r];
					upd();
					pos = Q[i][l-1];
					upd();
				}
				r--;
				l--;
			}
			else if (d != R - 1) {
				dir = 1;
				for (int i = l; i <=r ; i++) {
					pos = Q[h][i];
					upd();
					pos = Q[d + 1][i];
					upd();
				}
				h++;
				d++;
			}
			else break;
		 }
	}
	return ans;
	
	//return R*C/2;
}
//static int R,C,H,W,Q[3001][3001],i,j,ans;
/*
int main(){
	static int R,C,H,W,Q[3001][3001] = {},i,j;
   scanf("%d%d%d%d",&R,&C,&H,&W);
   for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
  // ans = 
  rectangle(R,C,H,W,Q);
   printf("%d\n",ans);
   return 0;
}
	 */

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 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 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 896 KB Output is correct
5 Correct 53 ms 1024 KB Output is correct
6 Correct 15 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 896 KB Output is correct
5 Correct 53 ms 1024 KB Output is correct
6 Correct 15 ms 896 KB Output is correct
7 Correct 1163 ms 3576 KB Output is correct
8 Correct 65 ms 3456 KB Output is correct
9 Correct 1179 ms 3452 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 896 KB Output is correct
5 Correct 53 ms 1024 KB Output is correct
6 Correct 15 ms 896 KB Output is correct
7 Correct 1163 ms 3576 KB Output is correct
8 Correct 65 ms 3456 KB Output is correct
9 Correct 1179 ms 3452 KB Output is correct
10 Execution timed out 5067 ms 23160 KB Time limit exceeded
11 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 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 25 ms 896 KB Output is correct
5 Correct 53 ms 1024 KB Output is correct
6 Correct 15 ms 896 KB Output is correct
7 Correct 1163 ms 3576 KB Output is correct
8 Correct 65 ms 3456 KB Output is correct
9 Correct 1179 ms 3452 KB Output is correct
10 Execution timed out 5067 ms 23160 KB Time limit exceeded
11 Halted 0 ms 0 KB -