結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー tails
提出日時 2024-12-12 11:09:09
言語 C90
(gcc 12.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
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

ソースコード

diff # 

#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);
}
0