QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149463 | #5711. Cars on Ice | lmeowdn | 25 ✓ | 441ms | 102760kb | C++14 | 2.3kb | 2023-08-24 17:21:21 | 2023-08-24 17:21:22 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
template<typename T,typename U> T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U> T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S> bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S> bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
typedef tuple<int,int,int> tii;
int n,m,deg[N][N][4],p[105],cnt;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char s[N][N];
vector<pii> ans;
bool in(int x,int y) {
return 1<=x&&x<=n&&1<=y&&y<=m;
}
signed main() {
n=read(), m=read();
p['N']=3, p['S']=1, p['E']=0, p['W']=2;
rep(i,1,n) scanf("%s",s[i]+1);
rep(i,1,n) rep(j,1,m) {
rep(t,0,3) deg[i][j][t]+=in(i+dx[t],j+dy[t]);
if(s[i][j]!='.') {
rep(t,0,3) if(t!=p[s[i][j]]) deg[i][j][t]++;
++cnt;
}
}
queue<tii>q;
rep(i,1,n) rep(j,1,m) rep(t,0,3)
if(!deg[i][j][t]) q.push(tii(i,j,t));
while(!q.empty()) {
auto [x,y,t]=q.front(); q.pop();
int nx=x-dx[t], ny=y-dy[t];
if(in(nx,ny)) {
--deg[nx][ny][t];
if(!deg[nx][ny][t]) q.push(tii(nx,ny,t));
}
if(s[x][y]!='.'&&t==p[s[x][y]]) {
ans.eb(x-1,y-1);
rep(t,0,3) if(t!=p[s[x][y]]) {
--deg[x][y][t];
if(!deg[x][y][t]) q.push(tii(x,y,t));
}
}
}
if(ans.size()!=cnt) puts("-1");
else for(auto [x,y]:ans) printf("(%d,%d)\n",x,y);
return 0;
}
詳細信息
Test #1:
score: 2.5
Accepted
time: 1ms
memory: 3812kb
input:
4 4 S... .E.. ..N. ...W
output:
(2,2) (1,1) (0,0) (3,3)
result:
ok all right!
Test #2:
score: 2.5
Accepted
time: 1ms
memory: 3744kb
input:
6 4 .... .... ...S .... ...W ....
output:
(4,3) (2,3)
result:
ok all right!
Test #3:
score: 2.5
Accepted
time: 1ms
memory: 3880kb
input:
10 10 ESESESESES SWNSNSNSNS EENSNSNSNS SWWWNSNSNS EEEENSNSNS SWWWWWNSNS EEEEEENSNS SWWWWWWWNS EEEEEEEENS SWWWWWWWWW
output:
(9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (8,9) (7,9) (6,9) (5,9) (4,9) (3,9) (2,9) (1,9) (0,9) (0,8) (1,8) (2,8) (3,8) (4,8) (5,8) (6,8) (7,8) (8,8) (8,7) (8,6) (8,5) (8,4) (8,3) (8,2) (8,1) (8,0) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (6,7) (5,7) (4,7) (3,7) (2,7) (1,7) ...
result:
ok all right!
Test #4:
score: 2.5
Accepted
time: 0ms
memory: 4572kb
input:
100 100 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEESSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEESSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEESSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
(99,0) (99,1) (99,2) (99,3) (99,4) (99,5) (99,6) (99,7) (99,8) (99,9) (99,10) (99,11) (99,12) (99,13) (99,14) (99,15) (99,16) (99,17) (99,18) (99,19) (99,20) (99,21) (99,22) (99,23) (99,24) (99,25) (99,26) (99,27) (99,28) (99,29) (99,30) (99,31) (99,32) (99,33) (99,34) (99,35) (99,36) (99,37) (99,38...
result:
ok all right!
Test #5:
score: 2.5
Accepted
time: 3ms
memory: 4588kb
input:
100 100 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEN NWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
(0,99) (0,98) (0,97) (0,96) (0,95) (0,94) (0,93) (0,92) (0,91) (0,90) (0,89) (0,88) (0,87) (0,86) (0,85) (0,84) (0,83) (0,82) (0,81) (0,80) (0,79) (0,78) (0,77) (0,76) (0,75) (0,74) (0,73) (0,72) (0,71) (0,70) (0,69) (0,68) (0,67) (0,66) (0,65) (0,64) (0,63) (0,62) (0,61) (0,60) (0,59) (0,58) (0,57)...
result:
ok all right!
Test #6:
score: 2.5
Accepted
time: 137ms
memory: 33140kb
input:
1000 1000 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
(0,999) (2,0) (4,999) (6,0) (8,999) (10,0) (12,999) (14,0) (16,999) (18,0) (20,999) (22,0) (24,999) (26,0) (28,999) (30,0) (32,999) (34,0) (36,999) (38,0) (40,999) (42,0) (44,999) (46,0) (48,999) (50,0) (52,999) (54,0) (56,999) (58,0) (60,999) (62,0) (64,999) (66,0) (68,999) (70,0) (72,999) (74,0) (...
result:
ok all right!
Test #7:
score: 2.5
Accepted
time: 103ms
memory: 33088kb
input:
1000 1000 SESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESESE...
output:
(0,999) (1,999) (2,999) (3,999) (4,999) (5,999) (6,999) (7,999) (8,999) (9,999) (10,999) (11,999) (12,999) (13,999) (14,999) (15,999) (16,999) (17,999) (18,999) (19,999) (20,999) (21,999) (22,999) (23,999) (24,999) (25,999) (26,999) (27,999) (28,999) (29,999) (30,999) (31,999) (32,999) (33,999) (34,...
result:
ok all right!
Test #8:
score: 2.5
Accepted
time: 60ms
memory: 25328kb
input:
1000 1000 .....................................................................................................................................................................................................................................................................................................
output:
(4,284) (2,399) (998,2) (998,998) (999,998)
result:
ok all right!
Test #9:
score: 2.5
Accepted
time: 354ms
memory: 80344kb
input:
1500 1500 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
(0,750) (0,751) (0,752) (0,753) (0,754) (0,755) (0,756) (0,757) (0,758) (0,759) (0,760) (0,761) (0,762) (0,763) (0,764) (0,765) (0,766) (0,767) (0,768) (0,769) (0,770) (0,771) (0,772) (0,773) (0,774) (0,775) (0,776) (0,777) (0,778) (0,779) (0,780) (0,781) (0,782) (0,783) (0,784) (0,785) (0,786) (0,7...
result:
ok all right!
Test #10:
score: 2.5
Accepted
time: 441ms
memory: 102760kb
input:
2000 2000 SWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
output:
(1999,1999) (1999,1998) (1999,1997) (1999,1996) (1999,1995) (1999,1994) (1999,1993) (1999,1992) (1999,1991) (1999,1990) (1999,1989) (1999,1988) (1999,1987) (1999,1986) (1999,1985) (1999,1984) (1999,1983) (1999,1982) (1999,1981) (1999,1980) (1999,1979) (1999,1978) (1999,1977) (1999,1976) (1999,1975) ...
result:
ok all right!