Submission #32984
Source Code Expand
#include<cmath>
#include<queue>
#include<cstdio>
#include<cassert>
#include<sys/time.h>
#include"porter.h"
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int INF=1<<29;
int L,S,sx,sy;
void init(int L,int S){
::L=L;
::S=S;
sx=sy=0;
}
void teleport(ll x,ll y,int &x2,int &y2){
// ll x_tmp=floor((double)(x*L+y*S)/(L*L+S*S));
// ll y_tmp=floor((double)(y*L-x*S)/(L*L+S*S));
ll a,b=L*L+S*S;
a=x*L+y*S; int x_tmp=(a>=0||a%b==0?a/b:a/b-1);
a=y*L-x*S; int y_tmp=(a>=0||a%b==0?a/b:a/b-1);
x2=x-(x_tmp*L-y_tmp*S);
y2=y-(y_tmp*L+x_tmp*S);
// [0,L)x[0,L)∪[L,L+S)x[0,S) の範囲に正規化
if(y2<L){
if(x2<0) x2+=L+S, y2+=S-L;
}
else{
while(!(0<=x2 && x2<L && 0<=y2 && y2<L) && !(L<=x2 && x2<L+S && 0<=y2 && y2<S)){
x2+=S, y2-=L;
}
}
assert((0<=x2 && x2<L && 0<=y2 && y2<L) || (L<=x2 && x2<L+S && 0<=y2 && y2<S));
}
ll gettime(){
struct timeval tv;
gettimeofday(&tv,NULL);
return 1000000LL*tv.tv_sec+tv.tv_usec;
}
int moveTo(int tx,int ty,int a,int b){
ll dx[]={a,b,-a,-b},dy[]={b,-a,-b,a};
static int d[1000][2000];
rep(y,S) rep(x,L+S) d[y][x]=INF;
d[sy][sx]=0;
queue< pair<int,int> > Q;
Q.push(make_pair(sx,sy));
while(!Q.empty()){
ll x=Q.front().first,y=Q.front().second; Q.pop();
if(x==tx && y==ty) break;
rep(i,4){
int x2,y2;
teleport(x+dx[i],y+dy[i],x2,y2);
if(d[y2][x2]==INF){
d[y2][x2]=d[y][x]+1;
Q.push(make_pair(x2,y2));
}
}
}
sx=tx;
sy=ty;
return d[ty][tx]<INF?d[ty][tx]:-1;
}
Submission Info
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
21 / 21 |
0 / 27 |
0 / 52 |
Status |
|
|
|
Set Name |
Test Cases |
Subtask1 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9 |
Subtask2 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask2/7, subtask2/8, subtask2/9 |
Subtask3 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask2/7, subtask2/8, subtask2/9, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask3/6, subtask3/7, subtask3/8, subtask3/9 |
Case Name |
Status |
Exec Time |
Memory |
subtask1/1 |
AC |
498 ms |
8180 KB |
subtask1/2 |
AC |
668 ms |
8448 KB |
subtask1/3 |
AC |
295 ms |
8060 KB |
subtask1/4 |
AC |
582 ms |
8184 KB |
subtask1/5 |
AC |
589 ms |
8188 KB |
subtask1/6 |
AC |
533 ms |
8188 KB |
subtask1/7 |
AC |
589 ms |
8448 KB |
subtask1/8 |
AC |
593 ms |
8056 KB |
subtask1/9 |
AC |
67 ms |
8320 KB |
subtask2/1 |
TLE |
2030 ms |
8068 KB |
subtask2/2 |
TLE |
2031 ms |
8444 KB |
subtask2/3 |
TLE |
2030 ms |
8700 KB |
subtask2/4 |
RE |
0 ms |
8708 KB |
subtask2/5 |
TLE |
2031 ms |
8440 KB |
subtask2/6 |
TLE |
2032 ms |
8444 KB |
subtask2/7 |
TLE |
2030 ms |
8572 KB |
subtask2/8 |
TLE |
2031 ms |
8572 KB |
subtask2/9 |
RE |
0 ms |
8444 KB |
subtask3/1 |
RE |
506 ms |
10108 KB |
subtask3/2 |
RE |
398 ms |
10108 KB |
subtask3/3 |
RE |
528 ms |
10108 KB |
subtask3/4 |
RE |
500 ms |
10108 KB |
subtask3/5 |
RE |
486 ms |
10084 KB |
subtask3/6 |
RE |
419 ms |
10112 KB |
subtask3/7 |
RE |
408 ms |
10104 KB |
subtask3/8 |
RE |
452 ms |
10108 KB |
subtask3/9 |
RE |
494 ms |
10104 KB |