QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149463#5711. Cars on Icelmeowdn25 ✓441ms102760kbC++142.3kb2023-08-24 17:21:212023-08-24 17:21:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-24 17:21:22]
  • 评测
  • 测评结果:25
  • 用时:441ms
  • 内存:102760kb
  • [2023-08-24 17:21:21]
  • 提交

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!