제출 #842396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842396		allin27x	축구 경기장 (IOI23_soccer)	C++17	19.50 / 100	247 ms	47384 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;
}

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; i++) for (int j=i+1; j<n; j++){
		if (!(sts[i] * sts[j])) return -1;
	}
	for (int i=0; i<n-1; i++){
		int d = 0;
		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);
}
// int main(){
// 	cout<<biggest_stadium(4,{
// 		{1,1,1,0},
// 		{0,0,0,0},
// 		{0,0,1,1},
// 		{1,1,1,1}
// 	});
// }

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