QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106599#5112. Where Am I?ballanceTL 9ms6776kbC++172.3kb2023-05-18 10:14:082023-05-18 10:14:10

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:14:10]
  • 评测
  • 测评结果:TL
  • 用时:9ms
  • 内存:6776kb
  • [2023-05-18 10:14:08]
  • 提交

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]);
			else if (num > maxi)
			{
				ans.clear();
				ans.insert(d[i][0]);
				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; cin >> m >> n;
	for (int i = 1; i <= n; i++)
		scanf("%s", a[i+250] + 251);
	//cout << a(4, 1) << ' ' << a(2, 2); exit(0);
	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);
}

详细

Test #1:

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

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

score: -100
Time Limit Exceeded

input:

2 1
.X

output:


result: