QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121554 | #6314. 过河卒 | myee | 100 ✓ | 345ms | 96564kb | C++11 | 4.5kb | 2023-07-08 13:58:37 | 2023-07-08 13:58:40 |
Judging History
answer
// 那就是希望。
// 即便需要取模,也是光明。
#include <algorithm>
#include <queue>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
uint Q[2000005],l,r;
inline voi clear(){l=r=0;}
inline voi push(uint p){Q[r++]=p;}
inline uint pop(){return Q[l++];}
inline bol empty(){return l==r;}
voi solve()
{
uint n,m,c=0;
static bol B[105];
scanf("%u%u",&n,&m),c=0;
uint b=-1,r1=-1,r2=-1;
for(uint i=0;i<n;i++)
{
static chr C[15];scanf("%s",C);
for(uint j=0;j<m;j++,c++){B[c]=C[j]!='#';if(C[j]=='O')(~r1?r2:r1)=c;else if(C[j]=='X')b=c;}
}
static bol G[2000005];
static uint Deg[2000005];
static std::vector<uint>Way[2000005];
for(uint i=0;i<2*c*c*c;i++)Deg[i]=0,G[i]=0,Way[i].clear();
uint bgn=b+c*(r1+c*r2);
clear(),push(bgn);G[bgn]=1;
while(!empty())
{
uint p=pop(),q;
b=p%c,r1=p/c%c,r2=p/c/c%c;
if(b==r1||b==r2||b<m)continue;
if(p>=c*c*c)
{
if(B[b-m]){Deg[p]++;Way[q=b-m+c*(r1+c*r2)].push_back(p);if(!G[q])push(q),G[q]=true;}
if(b%m&&B[b-1]){Deg[p]++;Way[q=b-1+c*(r1+c*r2)].push_back(p);if(!G[q])push(q),G[q]=true;}
if((b+1)%m&&B[b+1]){Deg[p]++;Way[q=b+1+c*(r1+c*r2)].push_back(p);if(!G[q])push(q),G[q]=true;}
}
else
{
if(r1>=m&&B[r1-m]&&r1-m!=r2)
{
Deg[p]++;Way[q=b+c*(r2<r1-m?r2+c*(r1-m+c):r1-m+c*(r2+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if(r1<(n-1)*m&&B[r1+m]&&r1+m!=r2)
{
Deg[p]++;Way[q=b+c*(r2<r1+m?r2+c*(r1+m+c):r1+m+c*(r2+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if(r1%m&&B[r1-1]&&r1-1!=r2)
{
Deg[p]++;Way[q=b+c*(r2<r1-1?r2+c*(r1-1+c):r1-1+c*(r2+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if((r1+1)%m&&B[r1+1]&&r1+1!=r2)
{
Deg[p]++;Way[q=b+c*(r2<r1+1?r2+c*(r1+1+c):r1+1+c*(r2+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if(r2>=m&&B[r2-m]&&r2-m!=r1)
{
Deg[p]++;Way[q=b+c*(r1<r2-m?r1+c*(r2-m+c):r2-m+c*(r1+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if(r2<(n-1)*m&&B[r2+m]&&r2+m!=r1)
{
Deg[p]++;Way[q=b+c*(r1<r2+m?r1+c*(r2+m+c):r2+m+c*(r1+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if(r2%m&&B[r2-1]&&r2-1!=r1)
{
Deg[p]++;Way[q=b+c*(r1<r2-1?r1+c*(r2-1+c):r2-1+c*(r1+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
if((r2+1)%m&&B[r2+1]&&r2+1!=r1)
{
Deg[p]++;Way[q=b+c*(r1<r2+1?r1+c*(r2+1+c):r2+1+c*(r1+c))].push_back(p);
if(!G[q])push(q),G[q]=true;
}
}
}
static bol Win[2000005];
static uint Step[2000005];
clear();
for(uint i=0;i<2*c*c*c;i++)if(G[i]){Win[i]=false,Step[i]=0;if(!Deg[i])push(i);}
while(!empty())
{
uint p=pop();
for(auto s:Way[p])if(!Win[s])
{
Win[s]=true,Step[s]=Step[p]+1;
for(auto t:Way[s])if(!Win[t]){_max(Step[t],Step[s]+1);if(!--Deg[t])push(t);}
}
}
if(Win[bgn])printf("Red %u\n",Step[bgn]);else if(Deg[bgn])puts("Tie");else printf("Black %u\n",Step[bgn]);
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint t;scanf("%*u%u",&t);
while(t--)solve();
return 0;
}
// 那就是希望。
// 即便需要取模,也是光明。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 97ms
memory: 74932kb
input:
1 10 10 10 .#......#. ..#....#.. #..#..#..# ..#.O..#.. .#......#. ...####... ##..X...## .......... .##.O####. .......... 10 10 .##..##... .....##... ..X#.#.... #........# ..#.#.#... .#...#.#.. #..#.#.#.. ..#..#.#.# ...##O#... ..##O#.#.. 4 1 O O # X 10 10 .##.....## ...#....## .#.#...#.. .O###..... #...
output:
Tie Black 0 Black 0 Tie Black 0 Tie Black 0 Black 0 Tie Tie
result:
ok 10 lines
Test #2:
score: 5
Accepted
time: 109ms
memory: 79356kb
input:
2 10 10 10 .#.####..# .##..##### ##.###X### #....####. .#.####### #.#O###.## ..##.####. ..######## ########## ##O#.#.### 10 10 ..#.###.## ......#..# ....#O.... #..#.....# ...#.##### .....#..#. ..#.....#O X#....###. #.....##.. .#..##.... 10 10 .......##. .O##...##. ..#....... ####..O... ....#...## .....
output:
Black 0 Tie Tie Black 0 Black 0 Tie Black 0 Tie Tie Black 0
result:
ok 10 lines
Test #3:
score: 5
Accepted
time: 63ms
memory: 69400kb
input:
3 10 10 10 ##.####### ###..###OO ##X####.## ...####### #..###...# ##...##### ##..#.#### ..##..##.# ###..#.#.# #.###..##. 10 10 .##..##... .....##... ..X#.#.... #........# ..#.#.#... .#...#.#.. #..#.#.#.. ..#..#.#.# ...##O#... ..##O#.#.. 10 10 .......... .X........ .......... .......... ..#....... .....
output:
Black 0 Black 0 Black 0 Black 0 Black 0 Tie Tie Tie Tie Tie
result:
ok 10 lines
Test #4:
score: 5
Accepted
time: 70ms
memory: 73480kb
input:
4 10 10 10 .#......#. ..#....#.. #..#..#..# ..#.O..#.. .#......#. ...####... ##..X...## .......... .##.O####. .......... 10 10 ...#.##... ..####.##. ###.###### .####O#.X# ...####..# .##O#..#.# ##.#..###. #.#.#....# .#.#####.# .##.#.#.## 3 2 OO ## #X 10 10 .##.##...# ..##..#.#O .#O#.#...# #.#.#..##. ...
output:
Tie Black 0 Black 0 Black 0 Black 0 Black 0 Tie Tie Tie Tie
result:
ok 10 lines
Test #5:
score: 5
Accepted
time: 68ms
memory: 66672kb
input:
5 10 10 10 .......... ....O..... .......... ...X...... .......... .......... .......... .......... ########## .......O.. 10 10 .......... ..O....... .......... .......... .......... X......... .......... .......... ########## .......O.. 10 1 . . . O . . . X # O 10 1 O . . . . . . X # O 10 10 ..........
output:
Red 9 Red 21 Black 12 Red 7 Black 8 Red 23 Black 14 Red 25 Red 23 Red 1
result:
ok 10 lines
Test #6:
score: 5
Accepted
time: 66ms
memory: 65084kb
input:
6 10 10 10 .....O.... .......... .......... .......... .......... .X........ .......... .......... ########## ...O...... 10 1 O . . . . . . X # O 10 10 .......... ..O....... .......... .......... .......... X......... .......... .......... ########## .......O.. 10 10 .......... .....O.... .............
output:
Red 17 Red 7 Red 21 Red 17 Black 2 Black 12 Black 6 Red 25 Red 23 Black 10
result:
ok 10 lines
Test #7:
score: 5
Accepted
time: 5ms
memory: 56656kb
input:
7 10 10 1 . O # . . X . # . O 10 1 O . . . . . . X . O 10 1 . . # O O # # . . X 5 1 O O . X . 10 1 O # . . . . . X . O 9 1 O # O . . . . . X 10 1 . . . . X O . # . O 10 1 O O . # . . . . . X 10 1 . . . . . . X . O O 10 1 O . . . # X # O . .
output:
Red 5 Red 7 Black 0 Black 2 Red 11 Black 10 Red 1 Red 11 Black 12 Red 1
result:
ok 10 lines
Test #8:
score: 5
Accepted
time: 1ms
memory: 58168kb
input:
8 10 10 1 . . # . X # . O # O 10 1 . O O . X . . . . . 10 1 O O . . . . . . . X 5 1 . # O X O 10 1 O # . . . . X . . O 9 1 O # O . . . . X . 10 1 # . . . X O . # . O 10 1 O O # # . . . . . X 10 1 # . . . . . X . O O 10 1 . # O . # O . X # .
output:
Red 3 Red 3 Red 9 Red 1 Red 9 Red 5 Red 1 Black 0 Red 11 Red 3
result:
ok 10 lines
Test #9:
score: 5
Accepted
time: 1ms
memory: 57708kb
input:
9 10 10 1 # O # . . X . # . O 10 1 O . . . X . . . . O 10 1 . . # O O . # . . X 5 1 O O . X . 10 1 O # . # . . . X . O 9 1 O . # O . . . X . 10 1 . . . . X O . . . O 10 1 O O . # # . . . . X 10 1 . . . . X . # . O O 10 1 . # O # O . . X # .
output:
Red 5 Red 5 Red 5 Black 2 Red 7 Red 5 Red 1 Red 9 Black 8 Red 3
result:
ok 10 lines
Test #10:
score: 5
Accepted
time: 158ms
memory: 83320kb
input:
10 10 10 10 .###..###. .....O...# .##.#..... ..##.##.X# ##......#. #...#..... ....##...# ..#..O##.# #..#.##... .....##.#. 10 10 #...##..#. #......##. ..##....#. #.#.##..#O .O...#.##. .....##.X. .###...... ....#.#.#. .......##. ###...##.# 10 10 #.#....... ..##..##.. ..##.#X..O ....#..... #..#....#. #...
output:
Red 7 Red 5 Red 3 Black 2 Red 9 Tie Tie Red 9 Red 9 Red 7
result:
ok 10 lines
Test #11:
score: 5
Accepted
time: 252ms
memory: 91316kb
input:
11 10 10 10 ...#.....# ..#....... ##.##.###. ##...#.##X .....#...# ...#.#.O.# ..#...#... .....#.... ......#..# #...#...O# 10 10 ..###O#O#. .#.###.##. ##..#..#.. ....#X.... ........## ........## #...##.... ...#..###. ........#. ..#...#.#. 10 10 ######...# O.X.O####. #.#.#.#... #.......#. ...##...#. ....
output:
Black 8 Black 0 Black 2 Tie Tie Red 9 Tie Red 9 Red 9 Red 1
result:
ok 10 lines
Test #12:
score: 5
Accepted
time: 206ms
memory: 96564kb
input:
12 10 10 10 ##..##..O. .#........ .#.......# .......... #......... .XO##..... #......... .......... .......... .......... 5 6 #.#### #.#### #.OO## #X#### ###### 10 10 ....###### .######### O...##.### .######### ....###### ####....#. ####.####. ####.O..#. #######.#. ####....#X 10 10 .......... .........
output:
Red 1 Black 2 Red 9 Tie Red 9 Black 6 Tie Tie Red 3 Tie
result:
ok 10 lines
Test #13:
score: 5
Accepted
time: 143ms
memory: 85068kb
input:
13 10 10 10 .##...#... .#####..## #..#..#..# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 .##......# ..#..##..O ...#.##... ##..#O..## ..#...#... ###.....#X ..#....... .##.#.#... .#.#.#..#. #......#.# 10 10 .........# .......... O......... .......... ....O..... ....
output:
Black 6 Red 9 Red 9 Red 9 Black 8 Tie Red 7 Red 7 Tie Tie
result:
ok 10 lines
Test #14:
score: 5
Accepted
time: 345ms
memory: 96196kb
input:
14 10 10 10 .......O.. .......... .......... O......... .......... .......... .......... .......... .......X.. .......... 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 .#..O...#. ...####... ##.X....## .......... .#.O..#... ....
output:
Red 27 Black 6 Tie Black 8 Red 17 Red 63 Black 12 Red 17 Black 16 Red 5
result:
ok 10 lines
Test #15:
score: 5
Accepted
time: 149ms
memory: 85660kb
input:
15 10 10 10 .########O .........# ########.# .........# .######### .......... #########. .......... .######### .......O.X 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 8 ####.... ...#..#. .###..#. ...#.O#. ##.#..#. ...####. .##...
output:
Black 102 Black 6 Red 13 Red 9 Tie Red 63 Red 93 Red 139 Red 45 Black 44
result:
ok 10 lines
Test #16:
score: 5
Accepted
time: 99ms
memory: 76072kb
input:
16 10 10 10 ....###### .######### O...##.### .######### ....###### ####....#. ####.####. ####.O..#. #######.#. ####....#X 10 10 .#..O...#. ...####... ##.X....## .......... .#.O..#... .#....#... .#....#... ..####.... .......... .......... 10 10 O######### #..#..#... ..#..#..## .#..#..#.. ...#..#..# ....
output:
Red 9 Tie Black 50 Red 333 Red 41 Black 6 Red 133 Black 24 Red 111 Red 101
result:
ok 10 lines
Test #17:
score: 5
Accepted
time: 205ms
memory: 90588kb
input:
17 10 10 10 ########## .......... .......... ..######## .......... #########. .O........ .......... #......... O#X....... 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 #.......O. ..#....... ...##.##.. .......... .......... ....
output:
Black 60 Black 6 Red 53 Red 35 Tie Tie Red 9 Red 65 Tie Red 63
result:
ok 10 lines
Test #18:
score: 5
Accepted
time: 145ms
memory: 82984kb
input:
18 10 10 10 O......... #..#..###. .#.##...#. ..X....... .####..... .##...##.# ...#..###. ...###..O# ..#..#.... .......### 10 10 ...#.....O ........#. ........X. .......... ...#...... .......... .........# .....O.... ..#....... .......... 10 10 ..O.#..... #.#...#... ...#..###. ....#..... ..#..#..#. #...
output:
Red 159 Tie Red 73 Black 36 Black 56 Black 6 Red 15 Black 0 Red 63 Black 2
result:
ok 10 lines
Test #19:
score: 5
Accepted
time: 159ms
memory: 85716kb
input:
19 10 10 10 .....#.... ...#.#.#.# #..#.##.#. .##.....#. .#..##.#.# ...#...... #.#.#.##.. ##...#O##. ..#.#O.... .#...#..X. 10 10 .O....#... .####....# .###...#.. .......... ###....##. ....#..##. .#.#.#.... .##.O#..#. #..#...#.. ...#....X# 10 10 O######### #..#..#... ..#..#..## .#..#..#.. ...#..#..# ....
output:
Black 6 Red 57 Black 50 Red 11 Tie Red 129 Red 99 Black 0 Red 111 Red 27
result:
ok 10 lines
Test #20:
score: 5
Accepted
time: 158ms
memory: 83928kb
input:
20 10 10 10 .##.....## ...#....## .#.#...#.. .O###..... ###....... ......###. .....#..O. ##........ ..#...X... .##....... 10 10 #...#.##.. .O##.....# #.#.....#. .#...#.... ....#..#.. .###...... ....O##.#. .#.#.....# .......... .#.#...X#. 10 10 ......###. ..#.#..##. .#.......# .#.#..###. ..#.#..#.. #...
output:
Tie Red 63 Red 61 Red 9 Black 6 Black 0 Tie Red 333 Red 57 Tie
result:
ok 10 lines
Extra Test:
score: 0
Extra Test Passed