QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106603#5112. Where Am I?ballanceTL 13ms6884kbC++172.3kb2023-05-18 10:29:012023-05-18 10:29:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-18 10:29:04]
  • 评测
  • 测评结果:TL
  • 用时:13ms
  • 内存:6884kb
  • [2023-05-18 10:29:01]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <sstream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<array>
#include<queue>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<unordered_map>
#include<random>
typedef unsigned long long ll;
typedef long double ld;
#define pii pair<int, int> 
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 2010;
//const ll x = 998244353, y = 1000000007;
void TLE() { while (1); }
void MLE() { while (1)int* a = new int[500000] {}; }
void RA() { set<int>a; cout << *a.end(); }
char a[750][750];
#define a(x,y) a[x+250][y+250]
int x, y;
int maxi;
set<pii>ans;
void turn()
{
	swap(x, y);
	y *= -1;
}
map<int, pii>b;
pii operator+(pii x, pii y)
{
	return make_pair(x.first + y.first, x.second + y.second);
}
int judge(pii& pos, pii& del)
{
	int x = (pos + del).first;
	int y = (pos + del).second;
	return a(x, y) == 'X' ? 1 : 0;
}
ll dfs(vector<pii>& c, int num = 0)
{
	vector<pii>d[2];
	ll sum = 0;
	for (auto& it : c)
		d[judge(it,b[num])].push_back(it);
	for (int i = 0; i <= 1; i++)
		if (d[i].size() > 1)
			sum+=dfs(d[i], num + 1);
		else if (!d[i].empty())
		{
			if (num == maxi)
				ans.insert({ -d[i][0].first,d[i][0].second });
			else if (num > maxi)
			{
				ans.clear();
				ans.insert({ -d[i][0].first,d[i][0].second });
				maxi = num;
			}
			sum += num;
		}
	return sum;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int cnt = 0, length = 1;
	x = -1, y = 0;
	int posx = 0, posy = 0;
	while (cnt < 50000)
	{
		for (int i = 0; i < length; i++)
		{
			posx += x, posy += y;
			b[++cnt] = make_pair(posx, posy);
		}
		turn();
		for (int i = 0; i < length; i++)
		{
			posx += x, posy += y;
			b[++cnt] = make_pair(posx, posy);
		}
		turn();
		++length;
	}
	int n, m; scanf("%d%d", &m, &n);
	for (int i = 1; i <= n; i++)
		scanf("%s", a[i+250] + 251);
	vector<pii>c;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			c.push_back({ i,j });
	ld ans1 = ld(dfs(c)) / (n * m);
	printf("%Lf\n", ans1);
	printf("%d\n", maxi);
	for (const pii& it : ans)
		printf("(%d,%d) ", it.second, it.first + n + 1);
}

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 6776kb

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 3ms
memory: 6820kb

input:

2 1
X.

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 13ms
memory: 6812kb

input:

1 2
.
X

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 12ms
memory: 6828kb

input:

1 2
X
.

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 12ms
memory: 6884kb

input:

2 1
XX

output:

3.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: -100
Time Limit Exceeded

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:


result: