QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177534#7120. Soccertriple321#14 270ms35444kbC++204.3kb2023-09-13 01:50:452023-09-13 01:50:45

Judging History

你现在查看的是测评时间为 2023-09-13 01:50:45 的历史记录

  • [2024-04-28 07:41:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:14
  • 用时:277ms
  • 内存:35336kb
  • [2023-09-13 01:50:45]
  • 评测
  • 测评结果:14
  • 用时:270ms
  • 内存:35444kb
  • [2023-09-13 01:50:45]
  • 提交

answer

#include <bits/stdc++.h>
#ifndef CYBER
#include "soccer.h"
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

lg dx[] = {1, 0, -1, 0};
lg dy[] = {0, 1, 0, -1}, N;

lg valid(lg i, lg j)
{
	return i >= 0 && i < N && j >= 0 && j < N;
}


int biggest_stadium(int n, vector<vector<int>> f)
{
	N = n;
	lg pos = 1, ans = 0, sum = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			ans += !f[i][j], sum += f[i][j];
			vector<int> tree[n];
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(f[i][j])
			{
				tree[i].push_back(j);
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		lg bef = 0, aft = 0;
		for(auto it : tree[i])
		{
			lg x = it;
			while(x >= 0)
			{
				bef += !f[i][x];
				x--;
			}
			x = it;
			while(x < n)
			{
				aft += !f[i][x];
				x++;
			}
		}
		if(bef && aft)	pos = 0;
		tree[i].clear();
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(f[i][j])
			{
				tree[j].push_back(i);
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		lg bef = 0, aft = 0;
		for(auto it : tree[i])
		{
			lg x = it;
			while(x >= 0)
			{
				bef += !f[x][i];
				x--;
			}
			x = it;
			while(x < n)
			{
				aft += !f[x][i];
				x++;
			}
		}
		if(bef && aft)	pos = 0;
	}
	set<lg> se[5];
	//down, right, up, left
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(f[i][j])	continue;
			if(i && j && f[i-1][j] && f[i][j-1])
			{
				auto it = se[4].lower_bound(i);
				if(it != se[4].begin())	pos = 0;
			}
			if(i+1 < n && j && f[i+1][j] && f[i][j-1])
			{
				auto it = se[4].upper_bound(i);
				if(it != se[4].end())	pos = 0;
			}
			if(i && f[i-1][j])
			{
				auto it = se[0].lower_bound(i);
				if(it != se[0].begin())	pos = 0;
			}
			if(i+1 < n && f[i+1][j])
			{
				auto it = se[2].upper_bound(i);
				if(it != se[2].end())	pos = 0;
			}
			if(j && f[i][j-1])
			{
				if(se[1].size())	pos = 0;
			}
			for(int k = 0; k < 4; k++)
			{
				lg newI = i+dx[k], newJ = j+dy[k];
				if(!valid(newI, newJ))	continue;
				if(f[newI][newJ])
				{
					se[k].insert((k%2 ? newI : newJ));
				}
			}
			se[4].insert(i);
		}
	}
	if(!pos)	ans = 1;
	if(sum == 1 && !pos)
	{
		int idI = 0, idJ = 0;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(f[i][j])
				{
					idI = i, idJ = j;
				}
			}
		}
		idI++;
		idJ++;
		// cout << idI << ' ' << idJ << '\n';
		// cout << idI*idJ << ' ' << idJ*(n-idI+1) << ' ' << idI*(n-idJ+1) << ' ' << (n-idJ+1)*(n-idI+1) << '\n';
		ans = n*n-min({idI*idJ, idJ*(n-idI+1), idI*(n-idJ+1), (n-idJ+1)*(n-idI+1)});
	}
	else if(n <= 3 && !pos)
	{
		for(int i = 0; i < (1ll << (n*n)); i++)
		{
			vector<array<lg, 2>> a;
			for(int j = 0; j < n*n; j++)
			{
				if((1ll << j)&i)
				{
					a.push_back({j/n, j%n});
				}
			}
			lg o = 1;
			for(auto it : a)
			{
				if(f[it[0]][it[1]])	o = 0;
				for(auto it2 : a)
				{
					if(it[0] == it2[0])
					{
						for(int j = min(it[1], it2[1]); j <= max(it[1], it2[1]); j++)
						{
							if(f[it[0]][j]) o = 0;
						}
						if(o)	continue;
					}
					if(it[1] == it2[1])
					{
						for(int j = min(it[0], it2[0]); j <= max(it[0], it2[0]); j++)
						{
							if(f[j][it[1]]) o = 0;
						}
						if(o)	continue;
					}
					lg d = 1, h = 1;
					if(!f[it[0]][it2[1]])	
					{
						for(int i = min(it[1], it2[1]); i <= max(it[1], it2[1]); i++)
						{
							if(f[it[0]][i])	d = 0;
						}
						for(int i = min(it[0], it2[0]); i <= max(it[0], it2[0]); i++)
						{
							if(f[i][it2[1]])	d = 0;
						}
						if(d)	continue;
					}
					if(!f[it2[0]][it[1]])	
					{
						for(int i = min(it[1], it2[1]); i <= max(it[1], it2[1]); i++)
						{
							if(f[it2[0]][i])	h = 0;
						}
						for(int i = min(it[0], it2[0]); i <= max(it[0], it2[0]); i++)
						{
							if(f[i][it[1]])	h = 0;
						}
						if(h)	continue;
					}
					o = 0;
					break;
				}
			}
			ans = max(ans, (lg)(o*a.size()));
		}
	}
	return ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 0ms
memory: 3884kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
1
0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

ok ok

Test #2:

score: 6
Accepted
time: 0ms
memory: 3856kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 0
0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
5

result:

ok ok

Test #3:

score: 6
Accepted
time: 1ms
memory: 3908kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
9850

result:

ok ok

Test #4:

score: 6
Accepted
time: 17ms
memory: 5832kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
500
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
236536

result:

ok ok

Test #5:

score: 6
Accepted
time: 270ms
memory: 35444kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
3786181

result:

ok ok

Test #6:

score: 6
Accepted
time: 0ms
memory: 3904kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
9
1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
80

result:

ok ok

Test #7:

score: 6
Accepted
time: 0ms
memory: 3828kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
10
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
99

result:

ok ok

Test #8:

score: 6
Accepted
time: 0ms
memory: 3780kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 0 0
0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
8

result:

ok ok

Test #9:

score: 6
Accepted
time: 0ms
memory: 3904kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 0 0
1 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
8

result:

ok ok

Subtask #2:

score: 8
Accepted

Test #10:

score: 8
Accepted
time: 1ms
memory: 4092kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 0
0 1 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
5

result:

ok ok

Test #11:

score: 8
Accepted
time: 0ms
memory: 3828kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 1 1
0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
5

result:

ok ok

Test #12:

score: 8
Accepted
time: 1ms
memory: 4116kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 0
1 1 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
5

result:

ok ok

Test #13:

score: 8
Accepted
time: 1ms
memory: 4116kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
1 0 0
1 0 1
0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
4

result:

ok ok

Test #14:

score: 8
Accepted
time: 1ms
memory: 3828kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 0
1 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
6

result:

ok ok

Test #15:

score: 8
Accepted
time: 0ms
memory: 3816kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
0 0 1
0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
7

result:

ok ok

Test #16:

score: 8
Accepted
time: 0ms
memory: 4116kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
0 0 0
0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
9

result:

ok ok

Test #17:

score: 8
Accepted
time: 1ms
memory: 3900kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 0
1 0 0
0 1 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
6

result:

ok ok

Test #18:

score: 8
Accepted
time: 0ms
memory: 3824kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
1 1 1
0 1 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
2

result:

ok ok

Test #19:

score: 8
Accepted
time: 0ms
memory: 3836kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
0 0 1
1 0 1
0 1 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
3

result:

ok ok

Test #20:

score: 8
Accepted
time: 0ms
memory: 3828kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
3
1 0 1
0 0 0
1 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
6

result:

ok ok

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #21:

score: 5.5
Acceptable Answer
time: 0ms
memory: 4096kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0
0 0 0 0 0 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

points 0.250 partial

Test #22:

score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0
0 0 0 0 1 0 0

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

points 0.250 partial

Test #23:

score: 5.5
Acceptable Answer
time: 0ms
memory: 4116kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
0 0 0 1 0 0 0
0 0 0 0 0 1 0
0 1 0 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 1 0 0
1 0 0 0 0 1 0
0 1 0 0 1 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

points 0.250 partial

Test #24:

score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
0 0 1 1 0 1 0
1 1 0 0 0 1 0
0 1 0 0 0 0 1
0 0 0 1 1 1 0
0 0 1 0 1 0 0
1 0 1 0 0 1 1
0 1 1 0 1 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

points 0.250 partial

Test #25:

score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
0 0 1 1 0 0 1
1 1 1 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 0 1 1
1 1 1 1 1 0 1
1 0 0 0 0 0 0
1 0 0 1 0 0 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

points 0.250 partial

Test #26:

score: 0
Wrong Answer
time: 0ms
memory: 3840kb

input:

R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L
7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 0 1 1
1 1 1 0 0 0 1
1 1 1 1 0 1 1
1 1 1 1 0 1 1

output:

xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0
OK
1

result:

wrong answer wrong

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%