QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106600 | #5112. Where Am I? | ballance | WA | 13ms | 6840kb | C++17 | 2.3kb | 2023-05-18 10:18:15 | 2023-05-18 10:18:19 |
Judging History
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; 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);
}
詳細信息
Test #1:
score: 100
Accepted
time: 13ms
memory: 6840kb
input:
1 1 X
output:
0.000000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 9ms
memory: 6820kb
input:
2 1 .X
output:
0.000000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 13ms
memory: 6796kb
input:
2 1 X.
output:
0.000000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 6ms
memory: 6816kb
input:
1 2 . X
output:
0.000000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 13ms
memory: 6816kb
input:
1 2 X .
output:
0.000000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 11ms
memory: 6824kb
input:
2 1 XX
output:
3.000000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: -100
Wrong Answer
time: 6ms
memory: 6836kb
input:
3 3 XXX X.X XXX
output:
3.111111 5 (3,2) (3,3)
result:
wrong answer Read (3,2) but expected (3,1)