結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー 👑 tails
提出日時 2021-12-09 12:42:33
言語 C(gnu17)
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -std=gnu17 -Wno-error=implicit-function-declaration -Wno-error=implicit-int -Wno-error=incompatible-pointer-types -Wno-error=int-conversion -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,008 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 80 ms
コンパイル使用メモリ 29,052 KB
最終ジャッジ日時 2026-02-22 08:39:06
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.c: In function 'f1':
main.c:58:17: error: too many arguments to function 'mmap'; expected 0, have 6
   58 |         char*rp=mmap(0l,1l<<25,1,2,0,0ll);
      |                 ^~~~ ~~
main.c:57:14: note: declared here
   57 |         char*mmap();
      |              ^~~~
main.c: In function 'f3':
main.c:126:17: error: implicit declaration of function 'write' [-Wimplicit-function-declaration]
  126 |                 write(1,"Impossible",10);
      |                 ^~~~~
main.c:140:9: error: implicit declaration of function '_exit' [-Wimplicit-function-declaration]
  140 |         _exit(0);
      |         ^~~~~
main.c:140:9: warning: incompatible implicit declaration of built-in function '_exit' [-Wbuiltin-declaration-mismatch]
main.c: At top level:
main.c:143:1: error: return type defaults to 'int' [-Wimplicit-int]
  143 | main(){
      | ^~~~

ソースコード

diff #
raw source code 

#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