Submission #842377

#	Time	Username	Problem	Language	Result	Execution time	Memory
842377		andrei_c1	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	246 ms	31824 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int ASC = 0;
const int DESC = 1;

void minSelf(int &x, int y) {
	if(y < x) {
		x = y;
	}
}

void maxSelf(int &x, int y) {
	if(y > x) {
		x = y;
	}
}

// a before b
int trend(const pii &a, const pii &b) {
	if(a.first >= b.first && a.second <= b.second) {
		return ASC;
	}
	if(a.first <= b.first && a.second >= b.second) {
		return DESC;
	}
	return -1;
}

int biggest_stadium(int n, std::vector<std::vector<int>> v)
{
	int x = -1, y = -1, cnt = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(v[i][j] == 1) {
				cnt++;
				x = i;
				y = j;
			}
		}
	}
	if(cnt == 1) {
		return n * n - min({(x + 1) * (y + 1), (x + 1) * (n - y), (n - x) * (y + 1), (n - x) * (n - y)});
	} else if(cnt == 0) {
		return n * n;
	}
	vector<vector<pii>> intervals;
	for(int i = 0; i < n; i++) {
		intervals.emplace_back(vector<pii>(0));
		int lst = -1;
		for(int j = 0; j < n; j++) {
			if(v[i][j] == 0 && lst == -1) {
				lst = j;
			} else if(v[i][j] == 1 && lst != -1) {
				intervals.back().emplace_back(lst, j - 1);
				lst = -1;
			}
		}
		if(lst != -1) {
			intervals.back().emplace_back(lst, n - 1);
		}
		if(intervals.back().size() == 0) {
			intervals.pop_back();
		}
	}
	if(false) {
		return 0;
	} else {
		if(!intervals.empty()) {
			for(const auto &row: intervals) {
				if(row.size() > 1) {
					return 0;
				}
			}
			int lst = ASC;
			pair<int, int> in = intervals[0][0];
			for(int i = 1; i < (int) intervals.size(); i++) {
				maxSelf(in.first, intervals[i][0].first);
				minSelf(in.second, intervals[i][0].second);
				if(in.first > in.second) {
					return 0;
				}
				int crt = trend(intervals[i - 1][0], intervals[i][0]);
				if(crt == -1) {
					return 0;
				}
				if(lst == ASC && crt == DESC) {
					lst = DESC;
				} else if(lst == DESC && crt == ASC) {
					return 0;
				}
			}
		}
		return n * n - cnt;
	}
	return 0;
}

/*
5
1 1 0 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 1 1
1 1 1 1 1
------------
5
1 1 0 1 1
1 0 0 0 1
1 0 0 1 1
1 1 0 1 1
1 1 1 1 1
*/

/*
    [-----]
   [--------]
  [-------------]
  	[---]
*/

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