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

Submission Time
Task C - ポーター・テレ・ポーター (Porter-Tele-Porter)
User fura2
Language IOI-Style C++ (GCC 5.4.1)
Score 21
Code Size 1586 Byte
Status TLE
Exec Time 2032 ms
Memory 10112 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 21 / 21 0 / 27 0 / 52
Status
AC × 9
AC × 9
TLE × 7
RE × 2
AC × 9
TLE × 7
RE × 11
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