oj.uz

답안 #406758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406758 2021-05-18T04:29:54 Z ngrace Rectangles (IOI19_rect) C++14
50 / 100
 1809 ms 190068 KB 
#include "rect.h"
#include <vector>
#include <iostream>
#include <set>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second

long long count_rectangles(std::vector<std::vector<int> > a) {
	long long out=0;
	int R=a.size();
	int C=a[0].size();

	bool subSix=true;
	for(int i=0;i<R;i++){//check for sub six
		for(int j=0;j<C;j++){
			if(a[i][j]>1){
				subSix=false;
				break;
			}
		}
		if(!subSix){
			break;
		}
	}

	if(subSix){
		//find sub rectangles with dp[i][j] = {min(dp[i-1][j-1].first, dp[i][j-1].first),
		//										min(dp[i-1][j-1].second, dp[i-1][j].second)}
		//then for each rectangle check the border.
		//can speed up by making so only consider if dp[i-1][j-1].first and dp[i][j-1].first are equal
		v<v<pii>> dp(R,v<pii>(C,{-1,-1}));
		for(int r=1;r<R-1;r++){
			for(int c=1;c<C-1;c++){
				if(a[r][c]==0){
					int f=r;
					int s=c;

					int r1=dp[r-1][c-1].fi;
					int r2=dp[r-1][c].fi;
					int c1=dp[r-1][c-1].se;
					int c2=dp[r][c-1].se;

					if(c1==c2 && c1!=-1){
						s=max(c1,1);
					}
					if(r1==r2 && r1!=-1){
						f=max(r1,1);
					}
					if(c1==-1 && c2!=-1){
						s=c2;
					}
					else if(r1==-1 && r2!=-1){
						f=r2;
					}

					dp[r][c]={f,s};
				}
			}
		}

		//check dp table
		/**for(int r=0;r<R;r++){
			for(int c=0;c<C;c++){
				cout<<"("<<dp[r][c].fi<<" "<<dp[r][c].se<<") ";
			}
			cout<<endl;
		}**/

		//dp table is now made
		//iterate from bottom right to top left
		//for every distinct dp[i][j] value check borders of that rect then mark as covered
		set<pii> checked;
		checked.insert({-1,-1});
		for(int r=R-1;r>0;r--){
			for(int c=C-1;c>0;c--){
				if(a[r][c]==0 && checked.find(dp[r][c])==checked.end()){
					checked.insert(dp[r][c]);
					int r1=dp[r][c].fi;
					int c1=dp[r][c].se;
					bool works=true;
					for(int i=r1;i<=r;i++){
						if(a[i][c1-1]==0 || a[i][c+1]==0){
							works=false;
							break;
						}
					}
					for(int j=c1;j<=c;j++){
						if(a[r1-1][j]==0 || a[r+1][j]==0){
							works=false;
							break;
						}
					}
					if(works){
						out++;
					}
				}
			}
		}
	}
	else if((R<=200 && C<=200) || R<=3){//sub one, two, three and five
		for(int r1=1;r1<R-1;r1++){
			for(int c1=1;c1<C-1;c1++){
				for(int r2=r1;r2<R-1;r2++){
					for(int c2=c1;c2<C-1;c2++){
						//have rect with top left r1, c1, bottom right r2, c2
						//check every value of the rect
						bool works=true;
						for(int r=r1;r<=r2;r++){
							for(int c=c1;c<=c2;c++){
								if(a[r1-1][c]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r2+1][c]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r][c1-1]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r][c2+1]<=a[r][c]){
									works=false;
									break;
								}
							}
							if(!works){
								break;
							}
						}
						if(works){
							out++;
						}
					}
				}
			}
		}
	}
	else{
		//full
	}

	return out;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 288 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 47 ms 344 KB Output is correct
23 Correct 48 ms 384 KB Output is correct
24 Correct 46 ms 352 KB Output is correct
25 Correct 36 ms 332 KB Output is correct
26 Correct 39 ms 332 KB Output is correct
27 Correct 39 ms 332 KB Output is correct
28 Correct 41 ms 332 KB Output is correct
29 Correct 11 ms 332 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 288 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 47 ms 344 KB Output is correct
18 Correct 48 ms 384 KB Output is correct
19 Correct 46 ms 352 KB Output is correct
20 Correct 36 ms 332 KB Output is correct
21 Correct 39 ms 332 KB Output is correct
22 Correct 39 ms 332 KB Output is correct
23 Correct 41 ms 332 KB Output is correct
24 Correct 11 ms 332 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1809 ms 820 KB Output is correct
31 Correct 1752 ms 816 KB Output is correct
32 Correct 1789 ms 964 KB Output is correct
33 Correct 1388 ms 676 KB Output is correct
34 Correct 1545 ms 740 KB Output is correct
35 Correct 1551 ms 892 KB Output is correct
36 Correct 1507 ms 872 KB Output is correct
37 Correct 1456 ms 844 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 288 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 47 ms 344 KB Output is correct
18 Correct 48 ms 384 KB Output is correct
19 Correct 46 ms 352 KB Output is correct
20 Correct 36 ms 332 KB Output is correct
21 Correct 39 ms 332 KB Output is correct
22 Correct 39 ms 332 KB Output is correct
23 Correct 41 ms 332 KB Output is correct
24 Correct 11 ms 332 KB Output is correct
25 Correct 1809 ms 820 KB Output is correct
26 Correct 1752 ms 816 KB Output is correct
27 Correct 1789 ms 964 KB Output is correct
28 Correct 1388 ms 676 KB Output is correct
29 Correct 1545 ms 740 KB Output is correct
30 Correct 1551 ms 892 KB Output is correct
31 Correct 1507 ms 872 KB Output is correct
32 Correct 1456 ms 844 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Incorrect 18 ms 7184 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 332 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 412 KB Output is correct
6 Correct 17 ms 404 KB Output is correct
7 Correct 16 ms 408 KB Output is correct
8 Correct 13 ms 392 KB Output is correct
9 Correct 15 ms 296 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 477 ms 87064 KB Output is correct
8 Correct 1016 ms 189064 KB Output is correct
9 Correct 999 ms 190044 KB Output is correct
10 Correct 987 ms 190068 KB Output is correct
11 Correct 94 ms 54628 KB Output is correct
12 Correct 170 ms 103680 KB Output is correct
13 Correct 209 ms 110632 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 288 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 47 ms 344 KB Output is correct
18 Correct 48 ms 384 KB Output is correct
19 Correct 46 ms 352 KB Output is correct
20 Correct 36 ms 332 KB Output is correct
21 Correct 39 ms 332 KB Output is correct
22 Correct 39 ms 332 KB Output is correct
23 Correct 41 ms 332 KB Output is correct
24 Correct 11 ms 332 KB Output is correct
25 Correct 1809 ms 820 KB Output is correct
26 Correct 1752 ms 816 KB Output is correct
27 Correct 1789 ms 964 KB Output is correct
28 Correct 1388 ms 676 KB Output is correct
29 Correct 1545 ms 740 KB Output is correct
30 Correct 1551 ms 892 KB Output is correct
31 Correct 1507 ms 872 KB Output is correct
32 Correct 1456 ms 844 KB Output is correct
33 Incorrect 18 ms 7184 KB Output isn't correct
34 Halted 0 ms 0 KB -