oj.uz

Submission #842392

# Submission time Handle Problem Language Result Execution time Memory
842392 2023-09-02T19:50:22 Z allin27x Soccer Stadium (IOI23_soccer) C++17
14 / 100
 238 ms 47636 KB 
#include <bits/stdc++.h>
using namespace std;

int TestCase1(int n, vector<vector<int>> a){
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (!a[i][j]) continue;
			int h = min(i+1, n-i);
			int v = min(j+1, n-j);
			return n*n-h*v;
		}
	}
	return n*n;
}

int TestCase2(int n, vector<vector<int>> a1){	
	int ans = 1;
	auto a = a1;
	for (int cd = 0; cd<(1<<(n*n)); cd++){
		a = a1;
		int bad = 0;
		for (int i=0; i<n; i++) for (int j=0; j<n; j++) 
			if (a[i][j] && !(cd&(1<<(n*i+j)))) bad = 1;
		if (bad) continue;
		for (int i=0; i<n; i++) for (int j=0; j<n; j++) a[i][j] = (bool) (cd & (1<<(n*i+j)));
		for (int x1 = 0; x1<n; x1++) for (int y1 = 0; y1<n; y1++){
			if (a[x1][y1]) continue;
			for (int x2 = 0; x2<n; x2++) for (int y2 = 0; y2<n; y2++){
				if (a[x2][y2]) continue;
				if (x1==x2 && y1==y2) continue;
				if (x1 == x2){
					for (int j=min(y1,y2); j<max(y1,y2); j ++){
						if (a[x1][j]) bad = 1;
					}
				}
				if (y1 == y2){
					for (int i=min(x1,x2); i<max(x1,x2); i++){
						if (a[i][y1]) bad =1;
					}
				}
				if (a[x1][y2] && a[x2][y1]) bad = 1;
				if (bad) break;
			}
			if (bad) break;
		}
		if (bad) continue;
		ans = max(ans, n*n - __builtin_popcount(cd));
	}
	return ans;
}

struct segment{
	int l=-1, r=-1;
	bool operator == (segment u){
		return l == u.l && r==u.r;
	}
	bool operator >= (segment u){
		if (u.l == -1) return 1;
		if (l==-1) return 0;
		return l<=u.l && r>=u.r;
	}
	bool operator *(segment u){
		if (l==-1 || u.l ==-1) return 1;
		if (l<u.l && r<u.r) return 0;
		if (l>u.l && r>u.r) return 0;
		return 1;
	}

};
int Partial(int n, vector<vector<int>> a){
	vector<segment> sts(n);
	int cnt = 0;
	for (int i=0; i<n; i++){
		int st = 0;
		for (int j=0; j<n; j++){
			cnt+=!a[i][j];
			if (!a[i][j] && !st){
				st = 1; sts[i].l = j; sts[i].r = j;
			} else if (!a[i][j] && st==1){
				sts[i].r = j;
			} else if (a[i][j] && st==1){
				st = 2;
			} else if (a[i][j] && !st) {}
			else if (a[i][j] && st==2) {}
			else return -1;
		}
	}
	// for (int i=0; i<n; i++) cout<<sts[i].l <<' '<<sts[i].r<<'\n';
	for (int i=0; i<n-1; i++){
		int d = 0;
		if (!(sts[i] * sts[i+1])) return -1;
		if (sts[i] == sts[i+1]) continue;
		if (sts[i+1]>=sts[i] && d) return -1;
		if (sts[i]>=sts[i+1] && !d) d=1;
	}
	return cnt;
}

int biggest_stadium(int n, vector<vector<int>> a){
	if (n<4) return TestCase2(n,a);
	int ones = 0;
	for(int i=0; i<n; i++) for (int j=0; j<n; j++) ones+=a[i][j];
	if (ones<=1) return TestCase1(n,a);
	return Partial(n,a);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 600 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 15 ms 3416 KB ok
9 Correct 238 ms 47636 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 600 KB ok
11 Correct 0 ms 600 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 0 ms 600 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 344 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 600 KB ok
12 Correct 0 ms 600 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 0 ms 600 KB ok
15 Partially correct 1 ms 344 KB partial
16 Partially correct 0 ms 344 KB partial
17 Partially correct 0 ms 344 KB partial
18 Partially correct 1 ms 344 KB partial
19 Partially correct 0 ms 348 KB partial
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Incorrect 0 ms 600 KB wrong
23 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 600 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 600 KB ok
14 Correct 0 ms 600 KB ok
15 Correct 1 ms 344 KB ok
16 Correct 0 ms 600 KB ok
17 Partially correct 1 ms 344 KB partial
18 Partially correct 0 ms 344 KB partial
19 Partially correct 0 ms 344 KB partial
20 Partially correct 1 ms 344 KB partial
21 Partially correct 0 ms 348 KB partial
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Incorrect 0 ms 600 KB wrong
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 600 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 600 KB ok
14 Correct 0 ms 600 KB ok
15 Correct 1 ms 344 KB ok
16 Correct 0 ms 600 KB ok
17 Partially correct 1 ms 344 KB partial
18 Partially correct 0 ms 344 KB partial
19 Partially correct 0 ms 344 KB partial
20 Partially correct 1 ms 344 KB partial
21 Partially correct 0 ms 348 KB partial
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Incorrect 0 ms 600 KB wrong
25 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 600 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 1 ms 344 KB ok
9 Correct 15 ms 3416 KB ok
10 Correct 238 ms 47636 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 344 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 600 KB ok
19 Correct 0 ms 600 KB ok
20 Correct 1 ms 344 KB ok
21 Correct 0 ms 600 KB ok
22 Partially correct 1 ms 344 KB partial
23 Partially correct 0 ms 344 KB partial
24 Partially correct 0 ms 344 KB partial
25 Partially correct 1 ms 344 KB partial
26 Partially correct 0 ms 348 KB partial
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Incorrect 0 ms 600 KB wrong
30 Halted 0 ms 0 KB -