結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー tailstails
提出日時 2023-03-10 12:15:54
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,220 bytes
コンパイル時間 602 ms
コンパイル使用メモリ 31,664 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-18 06:38:31
合計ジャッジ時間 1,762 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,348 KB
testcase_01 AC 0 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 0 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 2 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 0 ms
4,348 KB
testcase_11 AC 0 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 0 ms
4,348 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 1 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:8:59: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
    8 | #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
      |                                                           ^~~~~
main.c:123:9: note: in expansion of macro ‘wt1’
  123 |         wt1(z);
      |         ^~~
main.c:124:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  124 |         _exit(0);
      |         ^~~~~
main.c:124:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

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 rd20() ({long _s=*rp=='-'&&++rp,_v=rd();(_s?-_v:_v)&0xfffff;})
#define wt(v) ({unsigned _z=v;do*--wp=_z%10+48;while(_z/=10);})
#define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
#define rep(v,e) for(typeof(e) v=0;v<(e);++v)
#define MD 1000000007

unsigned const fac[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,227020758,178290591,674358851,789741546,425606191,660911389,557316307,146326063,72847302,602640637,860734560,657629300,440732388,459042011,394134213,35757887,36978716,109361473,390205642,486580460,57155068,943272305,14530444,523095984,354551275,472948359,444985875,799434881,776829897,626855450,954784168,10503098,472639410,741412713,846397273,627068824,726372166,318608048,249010336,948537388,272481214,713985458,269199917,75195247,286129051,595484846,133605669,16340084,996745124,798197261,286427093,331333826,536698543,422103593,280940535,103956247,172980994,108669496,715534167,518459667,847555432,719101534,932614679};
unsigned const ifac[]={1,1,500000004,166666668,41666667,808333339,301388891,900198419,487524805,831947206,283194722,571199524,380933296,490841026,320774361,821384963};

typedef unsigned long ulong;

void sort_aux(ulong*a,ulong*b,int n,int ph){
	int c[1024];
	for(int i=0;i<1024;++i){
		c[i]=0;
	}
	for(int i=0;i<n;++i){
		++c[a[i]&1023];
	}
	int t=0;
	for(int i=0;i<1024;++i){
		int u=c[i];
		c[i]=t;
		t+=u;
	}
	if(ph==0){
		for(int i=0;i<n;++i){
			b[c[a[i]&1023]++]=a[i]>>10|a[i]<<54;
		}
	}
	if(ph==1){
		for(int i=0;i<n;++i){
			b[c[a[i]&1023]++]=a[i]>>11|a[i]<<53;
		}
	}
	if(ph==2){
		for(int i=0;i<n;++i){
			b[c[a[i]&1023]++]=a[i]>>33|a[i]<<31;
		}
	}
}

int f1(ulong*a,int n,ulong*e,unsigned(*c)[46]){
	static ulong b[16*16*16];
	sort_aux(a,b,n,0);
	sort_aux(b,a,n,1);
	sort_aux(a,b,n,0);
	sort_aux(b,a,n,2);

	int m=0;
	rep(i,n){
		int c0=a[i]>>42&15;
		int c1=a[i]>>46&15;
		int c2=a[i]>>50&15;
		c[m][c0+c1+c2]=(c[m][c0+c1+c2]+1ull*ifac[c0]*ifac[c1]%MD*ifac[c2])%MD;
		if(i+1==n||(a[i]&(1ull<<42)-1)!=(a[i+1]&(1ull<<42)-1)){
			e[m]=a[i]&(1ull<<42)-1;
			++m;
		}
	}
	return m;
}

ulong d0[16*16],d1[16*16*16];
ulong e0[16*16],e1[16*16*16];
unsigned c0[16*16][46],c1[16*16*16][46];

int main(){
	rd_init();
	ulong gx=rd20();
	ulong gy=rd20();
	int k=rd();

	int m0=0;
	d0[m0++]=gy<<21|gx;
	rep(j,k<2?k:2){
		ulong x=-rd20()&0xfffff;
		ulong y=-rd20()&0xfffff;
		int n=rd();
		int e=m0*n;
		rep(i,e){
			d0[m0++]=d0[i]+(y<<21|x)+(1ull<<42+j*4)&~(1ull<<41|1ull<<20);
		}
	}
	m0=f1(d0,m0,e0,c0)-1;

	int m1=0;
	d1[m1++]=0;
	rep(j,k-2){
		ulong x=rd20();
		ulong y=rd20();
		int n=rd();
		int e=m1*n;
		rep(i,e){
			d1[m1++]=d1[i]+(y<<21|x)+(1ull<<42+j*4)&~(1ull<<41|1ull<<20);
		}
	}
	m1=f1(d1,m1,e1,c1)-1;

	ulong z=0;
	while((m0|m1)>=0){
		ulong xy0=e0[m0];
		ulong xy1=e1[m1];
		if(xy0==xy1){
			rep(i,31){
				if(c0[m0][i]){
					rep(j,46){
						if(c1[m1][j]){
							z=(z+1ull*c0[m0][i]*c1[m1][j]%MD*fac[i+j])%MD;
						}
					}
				}
			}
		}
		m0-=xy0>=xy1;
		m1-=xy0<=xy1;
	}
	wt1(z);
	_exit(0);
}
0