QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #504665 | #9108. Zayin and Obstacles | PhantomThreshold# | AC ✓ | 227ms | 12972kb | C++20 | 1.7kb | 2024-08-04 14:37:03 | 2024-08-04 14:37:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 105;
const int inf = 1e9;
int n,m;
int a[maxn][maxn][maxn],d[maxn][maxn][maxn];
int xi[3][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int Tcase; cin>>Tcase;
while(Tcase--)
{
cin>>n>>m;
memset(a,0,sizeof a);
memset(d,-1,sizeof d);
while(m--)
{
for(int j=0;j<2;j++)
{
for(int i=0;i<3;i++) cin>>xi[i][j];
}
for(int i=0;i<3;i++) xi[i][1]++;
for(int j1=0,s1=1;j1<2;j1++,s1=-s1) for(int j2=0,s2=1;j2<2;j2++,s2=-s2)
for(int j3=0,s3=1;j3<2;j3++,s3=-s3)
{
a[ xi[0][j1] ][ xi[1][j2] ][ xi[2][j3] ]+= s1*s2*s3;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
{
a[i][j][k]+=a[i][j][k-1];
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
{
a[i][j][k]+=a[i][j-1][k];
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
{
a[i][j][k]+=a[i-1][j][k];
}
for(int j=0;j<2;j++)
{
for(int i=0;i<3;i++) cin>>xi[i][j];
}
d[ xi[0][0] ][ xi[1][0] ][ xi[2][0] ]=0;
queue< tuple<int,int,int> >q;
q.emplace( xi[0][0], xi[1][0], xi[2][0] );
while(!q.empty())
{
const auto [x,y,z]= q.front(); q.pop();
for(int dx=-1;dx<=1;dx++) for(int dy=-1;dy<=1;dy++) for(int dz=-1;dz<=1;dz++)
{
int cnt= (dx==0) + (dy==0) + (dz==0);
if( cnt==2 )
{
int nx=x+dx, ny=y+dy, nz=z+dz;
if( a[nx][ny][nz]==0 && d[nx][ny][nz]==-1 && nx>=1 && nx<=n && ny>=1 && ny<=n && nz>=1 && nz<=n )
{
d[nx][ny][nz]= d[x][y][z]+1;
q.emplace( make_tuple(nx,ny,nz) );
}
}
}
}
cout<<d[ xi[0][1] ][ xi[1][1] ][ xi[2][1] ]<<'\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12584kb
input:
3 3 0 1 1 1 3 3 3 3 1 2 1 1 2 3 3 1 1 1 3 3 3 3 3 2 1 1 2 2 3 1 1 2 2 3 2 1 2 2 3 3 2 1 1 1 1 1 3
output:
6 -1 14
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 23ms
memory: 12824kb
input:
5 19 27 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 1 1 2 18 19 2 2 1 4 19 19 4 1 1 6 18 19 6 2 1 8 19 19 8 1 1 10 18 19 10 2 1 12 19 19 12 1 1 14 18 19 14 2 1 16 19 19 16 1 1 18 18 19 18 1 2 2 19 19 2 1 2 4 ...
output:
1998 15998 53998 127998 249998
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 79ms
memory: 12528kb
input:
5 99 147 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 9...
output:
132878 2596 227782 37198 90672
result:
ok 5 lines
Test #4:
score: 0
Accepted
time: 18ms
memory: 12792kb
input:
5 99 1000 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 ...
output:
4998 4998 4998 4998 4998
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 41ms
memory: 12632kb
input:
5 19 1000 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 4 13 10 4 19 12 6 5 5 6 6 18 6 16 4 6 18 11 8 6 10 8 17 19 14 10 7 14 17 12 2 4 4 2 5 15 4 5 10 4 7 17 12 1 2 12 2 9 12 8 10 12 18 15 16 19 2 16 19 8 8 1 ...
output:
-1 798 1906 3198 4998
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 227ms
memory: 12972kb
input:
5 100 0 92 81 37 11 85 14 100 0 16 48 91 61 65 58 100 0 87 25 52 83 7 45 100 0 80 95 16 62 5 80 100 0 33 33 50 48 82 3
output:
108 95 29 172 111
result:
ok 5 lines