oj.uz

Submission #652375

# Submission time Handle Problem Language Result Execution time Memory
652375 2022-10-22T10:21:11 Z ymm Quality Of Living (IOI10_quality) C++17
100 / 100
 1124 ms 184240 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 11 ms 3924 KB Output is correct
8 Correct 10 ms 3924 KB Output is correct
9 Correct 10 ms 3784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 11 ms 3924 KB Output is correct
8 Correct 10 ms 3924 KB Output is correct
9 Correct 10 ms 3784 KB Output is correct
10 Correct 114 ms 25772 KB Output is correct
11 Correct 108 ms 25820 KB Output is correct
12 Correct 54 ms 16412 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 11 ms 3924 KB Output is correct
8 Correct 10 ms 3924 KB Output is correct
9 Correct 10 ms 3784 KB Output is correct
10 Correct 114 ms 25772 KB Output is correct
11 Correct 108 ms 25820 KB Output is correct
12 Correct 54 ms 16412 KB Output is correct
13 Correct 1124 ms 184216 KB Output is correct
14 Correct 1113 ms 184240 KB Output is correct
15 Correct 982 ms 170212 KB Output is correct