QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106603 | #5112. Where Am I? | ballance | TL | 13ms | 6884kb | C++17 | 2.3kb | 2023-05-18 10:29:01 | 2023-05-18 10:29:04 |
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].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);
}
Details
Tip: Click on the bar to expand more detailed information
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............................................................................................