QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402717 | #7733. Cool, It’s Yesterday Four Times More | Godwang | RE | 4ms | 3760kb | C++14 | 4.2kb | 2024-05-01 11:33:18 | 2024-05-01 11:33:18 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define endl '\n'
const double pai = acos(-1);
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a)%mod; //% mod
a = (a * a)%mod; //% mod
n >>= 1;
}
return ans;
}
int dir[4][2] =
{
{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // d a w s
const double inf = 1000000000000000000;
const ll mod = 1e9 + 7, P1 = 13331;
const double eps = 1e-7;
const int N = 5e3 + 10, M = 3e6 + 10;
int t,hang,lie;
bool flag[M];
int vis[M];
string s[N];
int get(int hang1,int lie1,int hang2,int lie2)
{
return hang1*(lie+1)*(hang+1)*(lie+1)+lie1*(hang+1)*(lie+1)+hang2*(lie+1)+lie2;
}
void unget(int u,int &hang1,int &lie1,int &hang2,int &lie2)
{
lie2=u%(lie+1);
u/=(lie+1);
hang2=u%(hang+1);
u/=hang+1;
lie1=u%(lie+1);
u/=(lie+1);
hang1=u;
}
bool out(int hangg,int liee)
{
if(hangg<=0||hangg>hang||liee<=0||liee>lie||s[hangg][liee]=='O')
{
return 1;
}
return 0;
}
void bfs(int zhi)
{
vis[zhi]=zhi;
flag[zhi]=0;
queue<int > q;
q.push(zhi);
while (q.size())
{
int u=q.front();
q.pop();
int hang1,lie1,hang2,lie2;
unget(u,hang1,lie1,hang2,lie2);
rep(i,0,3)
{
int x1=hang1+dir[i][0],y1=lie1+dir[i][1];
int x2=hang2+dir[i][0],y2=lie2+dir[i][1];
if(out(x1,y1))
{
continue;
}
if(out(x2,y2))
{
flag[vis[u]]=1;
continue;
}
int temp=get(x1,y1,x2,y2);
if(vis[temp])
{
continue;
}
vis[temp]=zhi;
q.push(temp);
}
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("ain.txt", "r", stdin);freopen("aout.txt", "w", stdout);
cin>>t;
while(t--)
{
cin>>hang>>lie;
rep(i,0,(hang+1)*(lie+1)*(hang+1)*(lie+1))
{
vis[i]=0;
}
rep(i,1,hang)
{
cin>>s[i];
s[i]=' '+s[i];
}
int ans=0;
rep(i,1,hang)
{
rep(j,1,lie)
{
if(s[i][j]=='.')
{
bool flagg=1;
rep(ii,1,hang)
{
rep(jj,1,lie)
{
if(i==ii&&j==jj||s[ii][jj]=='O')
{
continue;
}
int zhi=get(i,j,ii,jj);
if(vis[zhi]==0)
{
bfs(zhi);
}
int temp=vis[zhi];
if(flag[ temp ]==0)
{
flagg=0;
goto ttt;
}
}
}
ttt:
if(flagg)
{
ans++;
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
3 1 0 0
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
200 2 4 OOO. OO.. 2 3 OOO .O. 3 3 O.O OOO OO. 4 1 . . O O 1 2 .O 1 1 . 2 5 .OO.. .O.O. 2 1 O O 1 1 O 1 3 .OO 5 1 O O . O . 5 2 O. .. O. .O .. 5 3 ... ... .OO ..O OOO 3 5 ..O.O .O.O. .OO.O 5 2 .O OO O. O. .. 2 1 O O 3 5 .O.OO O...O ..OO. 1 5 ..... 5 1 O . O . . 5 3 OOO OO. .OO OO. O.O 2 1 O . 5 2 O. ...
output:
3 0 0 2 1 1 3 0 0 1 0 7 9 4 4 0 6 5 2 0 1 6 4 5 2 0 0 5 3 3 1 4 1 0 7 5 2 3 7 3 0 6 2 2 2 0 4 6 6 3 3 2 3 5 2 1 0 3 3 4 4 2 2 0 7 6 4 8 5 3 2 5 2 1 2 1 4 0 0 2 5 1 4 6 6 1 6 2 2 3 4 5 2 1 0 1 9 3 4 11 0 3 2 1 0 0 4 3 1 4 3 8 3 0 3 6 2 5 1 3 3 4 0 2 11 2 2 4 0 4 4 6 2 1 2 3 0 5 0 16 4 3 2 6 0 8 3 3 1...
result:
ok 200 lines
Test #3:
score: 0
Accepted
time: 4ms
memory: 3704kb
input:
50 10 9 OOOO.O... O...O.OOO .....O... ..OO..O.O ...O..O.O ..OOO..O. ..OOO...O .OO.O..OO .O.O.OO.. .O..O.O.O 10 10 .O.OOO.OO. ...OOOOOOO ...O.O..O. .O.O..O... .O.O.OO..O ..OO.O..OO O....O..OO OO...OOOOO OO.OO.O..O .O.O.OOOOO 10 8 O..OOO.O O.OOOO.. O..OO.OO OO..OO.. .OOO..O. .OO.OO.O OOO..OO. ..O..OO....
output:
31 40 13 25 40 37 27 29 20 26 25 29 21 29 21 31 32 31 33 34 25 31 18 25 41 28 20 45 20 29 18 21 27 28 35 13 20 17 32 29 28 23 23 23 24 18 28 17 35 24
result:
ok 50 lines
Test #4:
score: -100
Runtime Error
input:
5 1 1000 ....O..OO..O..O..OO...OOO.OOOO.O...O....OOOOO.....OO..OOOO.O..O....OOOO..OO..OOOO......O.O.O..O..OO.OO.OO.O....O.O.O.O.O.OO..O.O.OO..O..OO..O.OOO...O...O.O.O..O....O.OO...O..O...O.OOO..OO.O..O.OO.O.O..OOOO..O.OO.O.O....O.OO.......OOOO....O.O.O.O..OOO.O.OO.OOO..O...O.O.O.O.OO.O.OOOO...O.OO.....