oj.uz

Submission #842361

# Submission time Handle Problem Language Result Execution time Memory
842361 2023-09-02T19:17:55 Z andrei_c1 Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 344 KB 
#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 + 1), (n - x + 1) * (y + 1), (n - x + 1) * (n - y + 1)});
	} 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 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Incorrect 0 ms 344 KB wrong
3 Halted 0 ms 0 KB -