#592400 (C) No.1315 渦巻洞穴

提出ソース

結果

問題	No.1315 渦巻洞穴
ユーザー	tails
提出日時	2020-12-12 05:36:14
言語	C (gcc 12.3.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	2,436 bytes
コンパイル時間	402 ms
コンパイル使用メモリ	33,184 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-20 01:57:24
合計ジャッジ時間	3,309 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	1 ms 4,348 KB
testcase_04	AC	1 ms 4,348 KB
testcase_05	AC	1 ms 4,348 KB
testcase_06	AC	1 ms 4,348 KB
testcase_07	AC	1 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	1 ms 4,348 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	1 ms 4,348 KB
testcase_13	AC	1 ms 4,348 KB
testcase_14	AC	1 ms 4,348 KB
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	1 ms 4,348 KB
testcase_17	AC	1 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	1 ms 4,348 KB
testcase_20	AC	1 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	1 ms 4,348 KB
testcase_24	AC	1 ms 4,348 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	1 ms 4,348 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	1 ms 4,348 KB
testcase_34	AC	1 ms 4,348 KB
testcase_35	AC	1 ms 4,348 KB
testcase_36	AC	1 ms 4,348 KB
testcase_37	AC	1 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	2 ms 4,348 KB
testcase_40	AC	1 ms 4,348 KB
testcase_41	AC	2 ms 4,348 KB
testcase_42	AC	2 ms 4,348 KB
testcase_43	AC	1 ms 4,348 KB
testcase_44	AC	1 ms 4,348 KB
testcase_45	AC	2 ms 4,348 KB
testcase_46	AC	2 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	2 ms 4,348 KB
testcase_49	AC	2 ms 4,348 KB
testcase_50	AC	1 ms 4,348 KB
testcase_51	AC	1 ms 4,348 KB
testcase_52	AC	1 ms 4,348 KB
testcase_53	AC	2 ms 4,348 KB
testcase_54	AC	2 ms 4,348 KB
testcase_55	AC	1 ms 4,348 KB
testcase_56	AC	2 ms 4,348 KB
testcase_57	AC	1 ms 4,348 KB
testcase_58	AC	1 ms 4,348 KB
testcase_59	AC	1 ms 4,348 KB
testcase_60	AC	1 ms 4,348 KB
testcase_61	AC	2 ms 4,348 KB
testcase_62	AC	1 ms 4,348 KB
testcase_63	AC	1 ms 4,348 KB
testcase_64	AC	1 ms 4,348 KB
testcase_65	AC	2 ms 4,348 KB
testcase_66	AC	1 ms 4,348 KB
testcase_67	AC	1 ms 4,348 KB
testcase_68	AC	1 ms 4,348 KB
testcase_69	AC	1 ms 4,348 KB
testcase_70	AC	2 ms 4,348 KB
testcase_71	AC	1 ms 4,348 KB
testcase_72	AC	1 ms 4,348 KB
testcase_73	AC	1 ms 4,348 KB
testcase_74	AC	1 ms 4,348 KB
testcase_75	AC	1 ms 4,348 KB
testcase_76	AC	1 ms 4,348 KB
testcase_77	AC	2 ms 4,348 KB
testcase_78	AC	1 ms 4,348 KB
testcase_79	AC	2 ms 4,348 KB
testcase_80	AC	1 ms 4,348 KB
testcase_81	AC	1 ms 4,348 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.c: In function 'locate':
main.c:15:20: warning: implicit declaration of function 'sqrt' [-Wimplicit-function-declaration]
   15 |         int r=(int)sqrt(s-1)+1&~1;
      |                    ^~~~
main.c:1:1: note: include '<math.h>' or provide a declaration of 'sqrt'
  +++ |+#include <math.h>
    1 | #pragma GCC optimize("Ofast")
main.c:15:20: warning: incompatible implicit declaration of built-in function 'sqrt' [-Wbuiltin-declaration-mismatch]
   15 |         int r=(int)sqrt(s-1)+1&~1;
      |                    ^~~~
main.c:15:20: note: include '<math.h>' or provide a declaration of 'sqrt'
main.c: In function 'numat':
main.c:34:20: warning: implicit declaration of function 'abs' [-Wimplicit-function-declaration]
   34 |         int r1=max(abs(x),abs(y));
      |                    ^~~
main.c:1:1: note: include '<stdlib.h>' or provide a declaration of 'abs'
  +++ |+#include <stdlib.h>
    1 | #pragma GCC optimize("Ofast")
main.c: At top level:
main.c:88:1: warning: return type defaults to 'int' [-Wimplicit-int]
   88 | main(){
      | ^~~~
main.c: In function 'main':
main.c:147:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  147 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:148:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
  148 |         _exit(0);
      |         ^~~~~
      |         _Exit

ソースコード

raw source code

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char*mmap();
#define RD(v) int v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}

#define WT(v) {int _z=v,_n=0;long _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}

static inline
int max(int a,int b){
	return a>b?a:b;
}

void locate(int s,int*px,int*py){
	int r=(int)sqrt(s-1)+1&~1;
	int r1=r>>1;
	int t=(r+1)*(r+1)-s;
	if(t<r){
		*px=r1-t;
		*py=r1;
	}else if(t-=r,t<r){
		*px=-r1;
		*py=r1-t;
	}else if(t-=r,t<r){
		*px=-r1+t;
		*py=-r1;
	}else if(t-=r,1){
		*px=r1;
		*py=-r1+t;
	}
}

int numat(int x,int y){
	int r1=max(abs(x),abs(y));
	int r=r1<<1;
	int t=r1==y?-x:r1==-x?r-y:r1==-y?r*2+x:r*3+y;
	return (r+1)*(r+1)-r1-t;
}

int vvs[33];
int cvs[200008];
char cpre[200008],wbuf[200040],*wp=wbuf;
int cpren;

int f1(int ox,int oy,int zx,int zy,int av){
	int ov=numat(ox,oy);
	while(!(ox==zx&&oy==zy)){
		int c;
		if(ox<zx){
			++ox;
			c=3;
		}else if(ox>zx){
			--ox;
			c=2;
		}else if(oy<zy){
			++oy;
			c=1;
		}else{
			--oy;
			c=0;
		}
		cpre[cpren]=c;
		int nv=numat(ox,oy);
		int vv=ov^nv;
		cvs[cpren]=vv;
		cpren++;
		int bw=31-__builtin_clz(vv);
		vvs[bw]=vv;
		av^=ov=nv;
	}
	return av;
}

int f2(int i,int n,int fv){
	for(;i<n;++i){
		*wp++="UDLR"[cpre[i]];
		int vv=cvs[i];
		int bw=31-__builtin_clz(vv);
		if(fv&1<<bw&&vv==vvs[bw]){
			*wp++="DURL"[cpre[i]];
			*wp++="UDLR"[cpre[i]];
			fv&=~(1<<bw);
		}
	}
	return fv;
}

main(){
	char*rp=mmap(0l,1l<<28,1,2,0,0ll);
	RD(s);
	RD(t);
	int sx,sy,tx,ty;
	locate(s,&sx,&sy);
	locate(t,&tx,&ty);

	int av=s;
	av=f1(sx,sy,0,0,av);
	int cprenhalf=cpren;
	av=f1(0,0,tx,ty,av);
	int k=abs(sx)+abs(sy)+abs(tx)+abs(ty);

	int fv=0,lv=0;
	for(int iv=1<<30;iv>=32;iv>>=1){
		if(av&iv){
			fv|=iv;
			av^=vvs[31-__builtin_clz(iv)];
			k+=2;
		}
	}
	if(av&16){
		lv|=16;
		av^=19^1; // 1 -> 1,6,19,6,1
		k+=4;
	}
	if(av&8){
		lv|=8;
		av^=8^1; // 1 -> 1,8,1
		k+=2;
	}
	if(av&4){
		lv|=4;
		av^=4^1; // 1 -> 1,4,1
		k+=2;
	}
	if(av&2){
		lv|=2;
		av^=2^1; // 1 -> 1,8,1
		k+=2;
	}
	if(av&1){
		lv|=1;
		av^=1; // 1 -> 1,2,3,2,1,2,1
		k+=6;
	}
	*wp++='0';
	*wp++='\n';
	WT(k);
	*wp++='\n';
	fv=f2(0,cprenhalf,fv);
	if(lv&16) *wp++='L',*wp++='L',*wp++='R',*wp++='R';
	if(lv&8) *wp++='D',*wp++='U';
	if(lv&4) *wp++='U',*wp++='D';
	if(lv&2) *wp++='R',*wp++='L';
	if(lv&1) *wp++='R',*wp++='U',*wp++='D',*wp++='L',*wp++='R',*wp++='L';
	fv=f2(cprenhalf,cpren,fv);
	*wp++=10;
	write(1,wbuf,wp-wbuf);
	_exit(0);
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード