oj.uz

답안 #160621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160621 2019-10-28T20:29:01 Z eggag32 Rectangles (IOI19_rect) C++17
37 / 100
 5000 ms 691904 KB 
#define __AVX__ 1
#define __AVX2__ 1
#define __SSE__ 1
#define __SSE2__ 1
#define __SSE2_MATH__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSSE3__ 1
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
#include <x86intrin.h>
#include "rect.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

ll count_rectangles(vector<vi> a){
	int n = a.size();
	int m = a[0].size();
	bool hor[n + 5][m + 5][m + 5];
	bool ver[m + 5][n + 5][n + 5];
	memset(ver, 0, sizeof(ver));
	memset(hor, 0, sizeof(hor));
	repn(i, 1, n - 1){
		int hor1[m + 5][m + 5];
		memset(hor1, 0, sizeof(hor1));
		repn(j, 1, m - 1) repn(k, j, m - 1){
			if(j == k){
				hor1[j][k] = a[i][j];
				if(hor1[j][k] < a[i][j - 1] && hor1[j][k] < a[i][k + 1]) hor[i][j][k] = 1;
			}
			else{
				hor1[j][k] = max(hor1[j][k - 1], a[i][k]);
				if(hor1[j][k] < a[i][j - 1] && hor1[j][k] < a[i][k + 1]) hor[i][j][k] = 1;
			}
		}
	}
	repn(j, 1, m - 1){
		int ver1[n + 5][n + 5];
		memset(ver1, 0, sizeof(ver1));
		repn(i, 1, n - 1) repn(k, i, n - 1){
			if(i == k){
				ver1[i][k] = a[i][j];
				if(ver1[i][k] < a[i - 1][j] && ver1[i][k] < a[k + 1][j]) ver[j][i][k] = 1;
			}
			else{
				ver1[i][k] = max(ver1[i][k - 1], a[k][j]);
				if(ver1[i][k] < a[i - 1][j] && ver1[i][k] < a[k + 1][j]) ver[j][i][k] = 1;
			}
		}
	}
	ll ans = 0;
	repn(i, 1, n - 1) repn(j, 1, m - 1) repn(k, i, n - 1) repn(l, j, m - 1){
		int f = 1;
		repn(x, i, k + 1){
			if(!hor[x][j][l] || !hor[x][j][l]){
				f = 0;
				break;
			}
		}	
		if(!f) continue;
		repn(x, j, l + 1){
			if(!ver[x][i][k] || !ver[x][i][k]){
				f = 0;
				break;
			}
		}
		if(!f) continue;
		ans++;
	}
	return ans;
}

/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 29 ms 1528 KB Output is correct
18 Correct 29 ms 1628 KB Output is correct
19 Correct 30 ms 1656 KB Output is correct
20 Correct 18 ms 1528 KB Output is correct
21 Correct 19 ms 1528 KB Output is correct
22 Correct 21 ms 1648 KB Output is correct
23 Correct 20 ms 1656 KB Output is correct
24 Correct 7 ms 888 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 380 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 29 ms 1528 KB Output is correct
18 Correct 29 ms 1628 KB Output is correct
19 Correct 30 ms 1656 KB Output is correct
20 Correct 18 ms 1528 KB Output is correct
21 Correct 19 ms 1528 KB Output is correct
22 Correct 21 ms 1648 KB Output is correct
23 Correct 20 ms 1656 KB Output is correct
24 Correct 7 ms 888 KB Output is correct
25 Correct 1055 ms 17740 KB Output is correct
26 Correct 1096 ms 17680 KB Output is correct
27 Correct 998 ms 17744 KB Output is correct
28 Correct 515 ms 17784 KB Output is correct
29 Correct 532 ms 17708 KB Output is correct
30 Correct 544 ms 17704 KB Output is correct
31 Correct 558 ms 17808 KB Output is correct
32 Correct 530 ms 17400 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 380 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 29 ms 1528 KB Output is correct
18 Correct 29 ms 1628 KB Output is correct
19 Correct 30 ms 1656 KB Output is correct
20 Correct 18 ms 1528 KB Output is correct
21 Correct 19 ms 1528 KB Output is correct
22 Correct 21 ms 1648 KB Output is correct
23 Correct 20 ms 1656 KB Output is correct
24 Correct 7 ms 888 KB Output is correct
25 Correct 1055 ms 17740 KB Output is correct
26 Correct 1096 ms 17680 KB Output is correct
27 Correct 998 ms 17744 KB Output is correct
28 Correct 515 ms 17784 KB Output is correct
29 Correct 532 ms 17708 KB Output is correct
30 Correct 544 ms 17704 KB Output is correct
31 Correct 558 ms 17808 KB Output is correct
32 Correct 530 ms 17400 KB Output is correct
33 Execution timed out 5063 ms 691904 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 74256 KB Output is correct
2 Correct 58 ms 53676 KB Output is correct
3 Correct 81 ms 74224 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 78 ms 74324 KB Output is correct
6 Correct 76 ms 74232 KB Output is correct
7 Correct 76 ms 74292 KB Output is correct
8 Correct 75 ms 74236 KB Output is correct
9 Correct 75 ms 74232 KB Output is correct
10 Correct 34 ms 37240 KB Output is correct
11 Correct 39 ms 43512 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 73 ms 45944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 29 ms 1528 KB Output is correct
18 Correct 29 ms 1628 KB Output is correct
19 Correct 30 ms 1656 KB Output is correct
20 Correct 18 ms 1528 KB Output is correct
21 Correct 19 ms 1528 KB Output is correct
22 Correct 21 ms 1648 KB Output is correct
23 Correct 20 ms 1656 KB Output is correct
24 Correct 7 ms 888 KB Output is correct
25 Correct 1055 ms 17740 KB Output is correct
26 Correct 1096 ms 17680 KB Output is correct
27 Correct 998 ms 17744 KB Output is correct
28 Correct 515 ms 17784 KB Output is correct
29 Correct 532 ms 17708 KB Output is correct
30 Correct 544 ms 17704 KB Output is correct
31 Correct 558 ms 17808 KB Output is correct
32 Correct 530 ms 17400 KB Output is correct
33 Execution timed out 5063 ms 691904 KB Time limit exceeded
34 Halted 0 ms 0 KB -