結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
ユーザー tailstails
提出日時 2021-12-09 12:42:33
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,008 bytes
コンパイル時間 1,445 ms
コンパイル使用メモリ 47,744 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-07-17 06:21:03
合計ジャッジ時間 2,662 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'f3':
main.c:126:17: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  126 |                 write(1,"Impossible",10);
      |                 ^~~~~
main.c:140:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
  140 |         _exit(0);
      |         ^~~~~
      |         _Exit
main.c: At top level:
main.c:143:1: warning: return type defaults to 'int' [-Wimplicit-int]
  143 | main(){
      | ^~~~

ソースコード

diff # 

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

#define rd_skip() while(*rp++>=48)
#define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}
#define rd_signed(v) long v=0;{long _c,_s;_s=*rp=='-'&&++rp;while(_c=*rp++-48,_c>=0)v=v*10+_c;v=_s?-v:v;}
#define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);}
#define rep(v,e) for(long v=0;v<e;++v)

#define NA (7l<<64-3)

struct M {
	long e[16][16];
};

static inline
struct M id(){
	struct M m;
	rep(y,16){
		rep(x,16){
			m.e[y][x]=NA;
		}
		m.e[y][y]=0;
	}
	return m;
}

static inline
struct M mul(struct M const*p,struct M const*q){
	struct M m;
	rep(y,16){
		rep(x,16){
			long v=NA;
			rep(z,16){
				long pv=p->e[y][z];
				long qv=q->e[z][x];
				long w=pv+qv;
				v=v>=w?v:w;
			}
			m.e[y][x]=v>NA/2?v:NA;
		}
	}
	return m;
}

long c[26],k[26];
long r[16];
struct M m[26];

void f0(){
	rep(i,26){
		m[i]=id();
	}
}

void f1(){
	char*mmap();
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	rep(i,26){
		long ci=*rp++-49;
		if(*rp>=48){
			ci=*rp++-39;
		}
		++rp;
		c[i]=ci;
	}
	rep(i,26){
		rd(ki);
		k[i]=ki;
	}
	rd_skip();
	while(*rp){
		char*s=rp;
		while(*rp++!=32);
		long a=*rp++-49;
		if(*rp>=48){
			a=*rp++-39;
		}
		++rp;
		long b=*rp++-49;
		if(*rp>=48){
			b=*rp++-39;
		}
		++rp;
		rd_signed(e);
		for(long i;i=*s++-65,i>=0;){
			{
				long v=m[i].e[b][a];
				m[i].e[b][a]=v>=e?v:e;
			}
			{
				long v=m[i].e[a][b];
				m[i].e[a][b]=v>=e?v:e;
			}
		}
	}
}

void f2(){
	rep(i,26){
		struct M b=id();
		struct M mi=m[i];
		long ki=k[i];
		while(ki){
			if(ki&1){
				b=mul(&b,&mi);
			}
			ki>>=1;
			mi=mul(&mi,&mi);
		}
		rep(j,16){
			r[j]+=b.e[j][c[i]];
			r[j]=r[j]>NA/2?r[j]:NA;
		}
	}
}

void f3(){
	long v=NA/2;
	rep(j,16){
		if(v<r[j]){
			v=r[j];
		}
	}
	if(v==NA/2){
		write(1,"Impossible",10);
	}else{
		char wbuf[64],*wp=wbuf+sizeof wbuf;
		long neg=0;
		if(v<0){
			neg=1;
			v=-v;
		}
		wt(v);
		if(neg){
			*--wp='-';
		}
		write(1,wp,wbuf+sizeof wbuf-wp);
	}
	_exit(0);
}

main(){
	f0();
	f1();
	f2();
	f3();
}
0