oj.uz

Submission #842413

# Submission time Handle Problem Language Result Execution time Memory
842413 2023-09-02T20:48:24 Z andrei_c1 Soccer Stadium (IOI23_soccer) C++17
6 / 100
 261 ms 31804 KB 
#include "soccer.h"
#include <bits/stdc++.h>

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

const int ASC = 0;
const int DESC = 1;
const int CACA = -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 CACA;
}

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().empty()) {
			intervals.pop_back();
		}
	}
	if(false) {
		return 0;
	} else {
		assert(!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 == CACA) {
				return 0;
			}
			if(lst == ASC && crt == DESC) {
				lst = DESC;
				int j = i - 2;
				while(j >= 0 && trend(intervals[j][0], intervals[i][0]) != CACA) {
					j--;
				}
				if(j >= 0) {
					return 0;
				}
			} 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
------------
3
0 0 1
0 0 0
1 0 0
*/

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 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 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 16 ms 2396 KB ok
9 Correct 261 ms 31804 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Partially correct 1 ms 344 KB partial
4 Partially correct 0 ms 348 KB partial
5 Partially correct 0 ms 344 KB partial
6 Partially correct 1 ms 344 KB partial
7 Partially correct 1 ms 344 KB partial
8 Correct 0 ms 344 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 0 ms 344 KB partial
11 Incorrect 1 ms 344 KB wrong
12 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 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Partially correct 1 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Partially correct 0 ms 344 KB partial
7 Partially correct 1 ms 344 KB partial
8 Partially correct 1 ms 344 KB partial
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Partially correct 0 ms 344 KB partial
12 Incorrect 1 ms 344 KB wrong
13 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 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 344 KB partial
9 Partially correct 1 ms 344 KB partial
10 Partially correct 1 ms 344 KB partial
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 0 ms 344 KB partial
14 Incorrect 1 ms 344 KB wrong
15 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 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 344 KB partial
9 Partially correct 1 ms 344 KB partial
10 Partially correct 1 ms 344 KB partial
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 0 ms 344 KB partial
14 Incorrect 1 ms 344 KB wrong
15 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 Correct 0 ms 344 KB ok
3 Correct 0 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 1 ms 344 KB ok
9 Correct 16 ms 2396 KB ok
10 Correct 261 ms 31804 KB ok
11 Partially correct 1 ms 344 KB partial
12 Partially correct 0 ms 348 KB partial
13 Partially correct 0 ms 344 KB partial
14 Partially correct 1 ms 344 KB partial
15 Partially correct 1 ms 344 KB partial
16 Correct 0 ms 344 KB ok
17 Correct 0 ms 348 KB ok
18 Partially correct 0 ms 344 KB partial
19 Incorrect 1 ms 344 KB wrong
20 Halted 0 ms 0 KB -