#1030890 (C90) No.2986 Permutation Puzzle

• 問題: No.2986 Permutation Puzzle
• ユーザー: tails
• 提出日時: 2024-12-12 11:09:09
• 言語: C90 (gcc 11.4.0)
• 結果: AC
• 実行時間: 8 ms / 2,000 ms
• コード長: 2,260 bytes
• コンパイル時間: 651 ms
• コンパイル使用メモリ: 29,696 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-12-12 11:09:12
• 合計ジャッジ時間: 2,690 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	0 ms; 5,248 KB
testcase_02	AC	0 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	0 ms; 5,248 KB
testcase_05	AC	0 ms; 5,248 KB
testcase_06	AC	0 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	0 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	0 ms; 5,248 KB
testcase_17	AC	0 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	1 ms; 5,248 KB
testcase_21	AC	3 ms; 5,248 KB
testcase_22	AC	0 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	4 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	4 ms; 5,248 KB
testcase_28	AC	2 ms; 5,248 KB
testcase_29	AC	6 ms; 5,248 KB
testcase_30	AC	3 ms; 5,248 KB
testcase_31	AC	2 ms; 5,248 KB
testcase_32	AC	4 ms; 5,248 KB
testcase_33	AC	2 ms; 5,248 KB
testcase_34	AC	1 ms; 5,248 KB
testcase_35	AC	7 ms; 5,248 KB
testcase_36	AC	4 ms; 5,248 KB
testcase_37	AC	5 ms; 5,248 KB
testcase_38	AC	2 ms; 5,248 KB
testcase_39	AC	6 ms; 5,248 KB
testcase_40	AC	4 ms; 5,248 KB
testcase_41	AC	8 ms; 5,248 KB
testcase_42	AC	0 ms; 5,248 KB
testcase_43	AC	4 ms; 5,248 KB

コンパイルメッセージ

main.c:33:1: warning: return type defaults to ‘int’ [-Wimplicit-int]
   33 | f(z){
      | ^
main.c: In function ‘f’:
main.c:33:1: warning: type of ‘z’ defaults to ‘int’ [-Wimplicit-int]
main.c:36:24: warning: implicit declaration of function ‘memcmp’ [-Wimplicit-function-declaration]
   36 |                 return memcmp(a,b,100)==0;
      |                        ^~~~~~
main.c:1:1: note: include ‘<string.h>’ or provide a declaration of ‘memcmp’
  +++ |+#include <string.h>
    1 | #pragma GCC optimize("Ofast")
main.c:36:35: warning: ‘memcmp’ argument 3 type is ‘int’ where ‘long unsigned int’ is expected in a call to built-in function declared without prototype [-Wbuiltin-declaration-mismatch]
   36 |                 return memcmp(a,b,100)==0;
      |                                   ^~~
<built-in>: note: built-in ‘memcmp’ declared here
main.c:50:25: warning: implicit declaration of function ‘memcpy’ [-Wimplicit-function-declaration]
   50 |                         memcpy(a[z][a[z+1][p][y]],a[z+1][y],10);
      |                         ^~~~~~
main.c:50:25: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’
main.c:50:25: warning: incompatible implicit declaration of built-in function ‘memcpy’ [-Wbuiltin-declaration-mismatch]
main.c:50:25: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’
main.c: In function ‘f2’:
main.c:108:17: warning: implicit declaration of function ‘memset’ [-Wimplicit-function-declaration]
  108 |                 memset(b,0,10);
      |                 ^~~~~~
main.c:108:17: note: include ‘<string.h>’ or provide a declaration of ‘memset’
main.c:108:17: warning: incompatible implicit declaration of built-in function ‘memset’ [-Wbuiltin-declaration-mismatch]
main.c:108:17: note: include ‘<string.h>’ or provide a declaration of ‘memset’
main.c: In function ‘f3’:
main.c:165:9: warning: implicit declaration of function ‘wr

ソースコード

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

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) {unsigned _z=v,_n=0;long _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}
#define rep(v,e) for(typeof(e)v=0;v<e;++v)

char wbuf[1<<25];
int n,k,m,h[4][3];
char a[5][10][10],b[10][10];

int gcd(int a,int b){
	if(a==0||b==0){
		return a+b;
	}
	int x=__builtin_ctz(a);
	int y=__builtin_ctz(b);
	a>>=x;
	b>>=y;
	int c;
	while(c=a-b){
		c>>=__builtin_ctz(c);
		if(c<0){
			b=-c;
		}else{
			a=c;
		}
	}
	return a<<(x<=y?x:y);
}

f(z){
#if 1
	if(z==0){
		return memcmp(a,b,100)==0;
	}
#else
	if(memcmp(a[z],b,100)==0){
		k-=z;
		return 1;
	}
	if(z==0){
		return 0;
	}
#endif
	--z;
	rep(p,n){
		rep(y,n){
			memcpy(a[z][a[z+1][p][y]],a[z+1][y],10);
		}
		if(f(z)){
			h[z][0]=1;
			h[z][1]=p;
			return 1;
		}
	}
	rep(p,n){
		rep(y,n){
			rep(x,n){
				a[z][y][a[z+1][x][p]]=a[z+1][y][x];
			}
		}
		if(f(z)){
			h[z][0]=0;
			h[z][1]=p;
			return 1;
		}
	}
	return 0;
}

void f1(){
	rd_init();
	n=rd();
	k=rd();
	rep(y,n){
		rep(x,n){
			int v;
			if(rp[1]>='0'){
				v=10;
				rp+=3;
			}else{
				v=*rp-'0';
				rp+=2;
			}
			a[k][y][x]=v-1;
		}
	}
	rep(y,n){
		rep(x,n){
			int v;
			if(rp[1]>='0'){
				v=10;
				rp+=3;
			}else{
				v=*rp-'0';
				rp+=2;
			}
			b[y][x]=v-1;
		}
	}
}

void f2(){
	rep(z,k){
		char b[10];
		memset(b,0,10);
		int d=1;
		if(h[z][0]){
			rep(x,n){
				if(!b[x]){
					int t=x;
					int c=0;
					while(!b[t]){
						b[t]=1;
						t=a[z+1][h[z][1]][t];
						++c;
					}
					d*=c/gcd(d,c);
				}
			}
		}else{
			rep(y,n){
				if(!b[y]){
					int t=y;
					int c=0;
					while(!b[t]){
						b[t]=1;
						t=a[z+1][t][h[z][1]];
						++c;
					}
					d*=c/gcd(d,c);
				}
			}
		}
		m+=h[z][2]=d-1;
	}
}

void f3(){
	char*wp=wbuf;
	wt(m);
	*wp++='\n';
	rep(z,k){
		int p=h[z][1];
		rep(i,h[z][2]){
			if(h[z][0]){
				*wp++='R';
				p=a[z+1][h[z][1]][p];
			}else{
				*wp++='C';
				p=a[z+1][p][h[z][1]];
			}
			*wp++=' ';
			if(p==9){
				*wp++='1';
				*wp++='0';
			}else{
				*wp++=p+'1';
			}
			*wp++='\n';
		}
	}
	write(1,wbuf,wp-wbuf);
}

int main(){
	f1();
	f(k);
	f2();
	f3();
	_exit(0);
}