Submission #842353

#	Time	Username	Problem	Language	Result	Execution time	Memory
842353		allin27x	Soccer Stadium (IOI23_soccer)	C++17	14 / 100	234 ms	47380 KiB

soccer

#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;
}

int Partial(int n, vector<vector<int>> a){
	vector<int> left(n,-1), right(n,-1);
	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; left[i] = j;
			} else if (!a[i][j] && st==1){
				right[i] = 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-1; i++){
		int d = 0;
		int l1=left[i], r1=right[i], l2=left[i+1], r2=right[i+1];
		if (l1<l2 && r1<r2) return -1;
		if (l1>l2 && r1>r2) return -1;
		if (l1>l2 || r1>r2 && !d) d=1;
		else if (l1>l2 || r1>r2) return -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);
}

Compilation message (stderr)

soccer.cpp: In function 'int Partial(int, std::vector<std::vector<int> >)':
soccer.cpp:75:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   75 |   if (l1>l2 || r1>r2 && !d) d=1;
      |                ~~~~~~^~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30