結果
問題 | No.619 CardShuffle |
ユーザー |
![]() |
提出日時 | 2017-12-29 20:56:25 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 89 ms / 3,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 797 ms |
コンパイル使用メモリ | 29,952 KB |
実行使用メモリ | 7,220 KB |
最終ジャッジ日時 | 2024-12-22 23:21:54 |
合計ジャッジ時間 | 3,686 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 35 |
コンパイルメッセージ
main.c:1:7: warning: type defaults to 'int' in declaration of 'mod' [-Wimplicit-int] 1 | const mod=1000000007; | ^~~ main.c:9:1: warning: data definition has no type or storage class 9 | idx[1<<17]; | ^~~ main.c:9:1: warning: type defaults to 'int' in declaration of 'idx' [-Wimplicit-int] main.c:10:1: warning: data definition has no type or storage class 10 | CN; | ^~ main.c:10:1: warning: type defaults to 'int' in declaration of 'CN' [-Wimplicit-int] main.c:11:1: warning: data definition has no type or storage class 11 | N,Q,X,Y,x,y; | ^ main.c:11:1: warning: type defaults to 'int' in declaration of 'N' [-Wimplicit-int] main.c:11:3: warning: type defaults to 'int' in declaration of 'Q' [-Wimplicit-int] 11 | N,Q,X,Y,x,y; | ^ main.c:11:5: warning: type defaults to 'int' in declaration of 'X' [-Wimplicit-int] 11 | N,Q,X,Y,x,y; | ^ main.c:11:7: warning: type defaults to 'int' in declaration of 'Y' [-Wimplicit-int] 11 | N,Q,X,Y,x,y; | ^ main.c:11:9: warning: type defaults to 'int' in declaration of 'x' [-Wimplicit-int] 11 | N,Q,X,Y,x,y; | ^ main.c:11:11: warning: type defaults to 'int' in declaration of 'y' [-Wimplicit-int] 11 | N,Q,X,Y,x,y; | ^ main.c:45:1: warning: return type defaults to 'int' [-Wimplicit-int] 45 | d(i){ | ^ main.c: In function 'd': main.c:45:1: warning: type of 'i' defaults to 'int' [-Wimplicit-int] main.c:49:25: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration] 49 | scanf("%c%*c",&C[i].o); | ^~~~~ main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf' +++ |+#include <stdio.h> 1 | const mod=1000000007; main.c:49:25: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch] 49 | scanf("%c%*c",&C[i].o); | ^~~~
ソースコード
const mod=1000000007; typedef struct{ long long a,b,c; char o; }abc; abc C[1<<18],t,u; idx[1<<17]; CN; N,Q,X,Y,x,y; char T; abc op(char o,abc A,abc B){ abc R; if(o){ if(A.b>=0){ if(B.b>=0){ R.a=A.a; R.b=(A.b+A.c*B.a+B.b)%mod; R.c=B.c; }else{ R.a=A.a; R.b=A.b; R.c=A.c*B.a%mod; } }else{ if(B.b>=0){ R.a=A.c*B.a%mod; R.b=B.b; R.c=B.c; }else{ R.b=-(R.c=R.a=A.c*B.a%mod); } } }else{ R.a=A.a; R.b=(A.b+A.c+B.a+B.b)%mod; R.c=B.c; } R.o=o; return R; } d(i){ if(i<65536){ d(i*2); if(CN<N){ scanf("%c%*c",&C[i].o); C[idx[++CN]=i].o^='+'; d(i*2+1); } C[i]=op(C[i].o,C[i*2],C[i*2+1]); }else{ scanf("%lld%*c",&C[i].a); C[idx[++CN]=i].b=-(C[i].c=C[i].a); } } r(i){ C[i]=op(C[i].o,C[i*2],C[i*2+1]); i&&r(i/2); } main(){ d(scanf("%d%*c",&N)); for(scanf("%d%*c",&Q);~scanf("%c%d%d%*c",&T,&X,&Y);){ t=C[x=idx[X]]; u=C[y=idx[Y]]; if(T=='!'){ C[x]=u; C[y]=t; r(x>>X%2); r(y>>Y%2); }else{ for(;x/2<y/2;x/=2,y/=2){ t=x%2?t:op(C[x/2].o,t,C[x+1]); u=y%2?op(C[y/2].o,C[y-1],u):u; } t=op(C[x/2].o,t,u); printf("%lld\n",(t.a+t.b+t.c)%mod); } } }