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

提出ソース

結果

問題	No.1315 渦巻洞穴
ユーザー	tails
提出日時	2020-12-12 04:03:55
言語	C (gcc 12.3.0)
結果	WA
実行時間	-
コード長	2,022 bytes
コンパイル時間	309 ms
コンパイル使用メモリ	31,616 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-19 21:44:23
合計ジャッジ時間	3,004 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

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

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

コンパイルメッセージ

main.c: In function 'locate':
main.c:7:20: warning: implicit declaration of function 'sqrt' [-Wimplicit-function-declaration]
    7 |         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 | static inline
main.c:7:20: warning: incompatible implicit declaration of built-in function 'sqrt' [-Wbuiltin-declaration-mismatch]
    7 |         int r=(int)sqrt(s-1)+1&~1;
      |                    ^~~~
main.c:7:20: note: include '<math.h>' or provide a declaration of 'sqrt'
main.c: In function 'numat':
main.c:25:19: warning: implicit declaration of function 'abs' [-Wimplicit-function-declaration]
   25 |         int r=max(abs(x),abs(y))<<1;
      |                   ^~~
main.c:1:1: note: include '<stdlib.h>' or provide a declaration of 'abs'
  +++ |+#include <stdlib.h>
    1 | static inline
main.c: In function 'f1':
main.c:66:25: warning: implicit declaration of function 'putchar' [-Wimplicit-function-declaration]
   66 |                         putchar(c);
      |                         ^~~~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'putchar'
  +++ |+#include <stdio.h>
    1 | static inline
main.c: At top level:
main.c:82:1: warning: return type defaults to 'int' [-Wimplicit-int]
   82 | main(){
      | ^~~~
main.c: In function 'main':
main.c:84:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   84 |         scanf("%d%d",&s,&t);
      |         ^~~~~
main.c:84:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:84:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
main.c:84:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:127:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
  127 |         printf("0\n");
      |         ^~~~~~
main.c:127:9: note: include '<s

ソースコード

raw source code

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 t=(r+1)*(r+1)-s;
	if(t<r){
		*px=(r>>1)-t;
		*py=(r>>1);
	}else if(t-=r,t<r){
		*px=-(r>>1);
		*py=(r>>1)-t;
	}else if(t-=r,t<r){
		*px=-(r>>1)+t;
		*py=-(r>>1);
	}else if(t-=r,1){
		*px=(r>>1);
		*py=-(r>>1)+t;
	}
}

int numat(int x,int y){
	int r=max(abs(x),abs(y))<<1;
	int t;
	if((r>>1)==y){
		t=-x;
	}else if((r>>1)==-x){
		t=r-y;
	}else if((r>>1)==-y){
		t=r*2+x;
	}else{
		t=r*3+y;
	}
	return (r+1)*(r+1)-(r>>1)-t;
}

int vvs[33];

int f1(int ox,int oy,int zx,int zy,int outq,int fv){
	while(!(ox==zx&&oy==zy)){
		int nx,ny,c,crev;
		if(ox<zx){
			nx=ox+1;
			ny=oy;
			c='R'; crev='L';
		}else if(ox>zx){
			nx=ox-1;
			ny=oy;
			c='L'; crev='R';
		}else if(oy<zy){
			nx=ox;
			ny=oy+1;
			c='D'; crev='U';
		}else{
			nx=ox;
			ny=oy-1;
			c='U'; crev='D';
		}
		int ov=numat(ox,oy);
		int nv=numat(nx,ny);
		int vv=ov^nv;
		int bw=32-__builtin_clz(vv);
		if(outq){
			putchar(c);
			if(bw>=5&&fv&1<<bw&&vv==vvs[bw]){
				putchar(crev);
				putchar(c);
				fv&=~(1<<bw);
			}
		}else{
			vvs[bw]=vv;
			fv^=nv;
		}
		ox=nx;
		oy=ny;
	}
	return fv;
}

main(){
	int s,t;
	scanf("%d%d",&s,&t);
	int sx,sy,tx,ty;
	locate(s,&sx,&sy);
	locate(t,&tx,&ty);

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

	int fv=0;
	for(int iv=1<<30;iv>=32;iv>>=1){
		if(av&iv){
			fv|=iv;
			av^=vvs[32-__builtin_clz(iv)];
			k+=2;
		}
	}
	if(av&16){
		fv|=16;
		av^=19^1; // 1 -> 1,6,19,6,1
		k+=4;
	}
	if(av&8){
		fv|=8;
		av^=8^1; // 1 -> 1,8,1
		k+=2;
	}
	if(av&4){
		fv|=4;
		av^=4^1; // 1 -> 1,4,1
		k+=2;
	}
	if(av&2){
		fv|=2;
		av^=2^1; // 1 -> 1,8,1
		k+=2;
	}
	if(av&1){
		fv|=1;
		av^=1; // 1 -> 1,2,3,2,1,2,1
		k+=6;
	}
	printf("0\n");
	printf("%d\n",k);
	fv=f1(sx,sy,0,0,1,fv);
	if(fv&16) printf("LLRR");
	if(fv&8) printf("DU");
	if(fv&4) printf("UD");
	if(fv&2) printf("RL");
	if(fv&1) printf("RUDLRL");
	fv=f1(0,0,tx,ty,1,fv);
	putchar(10);
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード