Submission #652375

#	Time	Username	Problem	Language	Result	Execution time	Memory
652375		ymm	Quality Of Living (IOI10_quality)	C++17	100 / 100	1124 ms	184240 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 3010;
int sum[N];
int sump = 0;
int pi=0, pj=0;
int n, m, h, w;
bool marked[N][N];
pii pos[N*N];

bool mv()
{
	while (sump > h*w/2) {
		if (pi+h < n) {
			sump -= sum[pi];
			sump += sum[pi+h];
			++pi;
		} else if (pj+w < m) {
			Loop (i,0,n) {
				sum[i] -= marked[i][pj];
				sum[i] += marked[i][pj+w];
			}
			pi = 0;
			pj = pj+1;
			sump = 0;
			Loop (i,0,h)
				sump += sum[i];
		} else {
			return 0;
		}
	}
	return 1;
}

void mark(int i, int j)
{
	if (pi <= i && i < pi+h && pj <= j && j < pj+w)
		sump++;
	if (pj <= j && j < pj+w)
		sum[i]++;
	marked[i][j] = 1;
}

int rectangle(int _R, int _C, int _H, int _W, int Q[3001][3001])
{
	n = _R; m = _C; h = _H; w = _W;
	Loop (i,0,n) Loop (j,0,m)
		pos[Q[i][j]-1] = {i, j};
	LoopR (x,0,n*m) {
		mark(pos[x].first, pos[x].second);
		if (!mv())
			return x+1;
	}
	return -1;
}

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