結果
問題 | No.234 めぐるはめぐる (4) |
ユーザー |
![]() |
提出日時 | 2015-04-30 19:07:03 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 11,187 bytes |
コンパイル時間 | 1,249 ms |
コンパイル使用メモリ | 158,948 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 17:12:53 |
合計ジャッジ時間 | 1,775 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
コンパイルメッセージ
main.cpp: In function ‘void reader(double*)’: main.cpp:15:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 15 | void reader(double *x){scanf("%lf",x);} | ~~~~~^~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,a,b) for(i=a;i<b;i++)#define rep(i,n) REP(i,0,n)#define mygc(c) (c)=getchar_unlocked()#define mypc(c) putchar_unlocked(c)#define ll long long#define ull unsigned llvoid reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}void reader(double *x){scanf("%lf",x);}int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}void writer(double x, char c){printf("%.15f",x);mypc(c);}void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}template<class T> void writerLn(T x){writer(x,'\n');}template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}/*#define BIG_INT_SIZE 3#define BIG_INT_BASE 1000000000000000LL#define BIG_INT_DIGITS 15#define BIG_INT_CHAR_SIZE 1000typedef struct big_integer{ll a[BIG_INT_SIZE];}bigInt;int bigIntSign(bigInt a);int bigIntToChar(bigInt a,char ret[]);void printBigInt(bigInt a);void putBigInt(bigInt a);bigInt bigIntZero(){bigInt a; int i;rep(i,BIG_INT_SIZE) a.a[i]=0;return a;}bigInt bigIntOne(){bigInt a; int i;REP(i,1,BIG_INT_SIZE) a.a[i]=0; a.a[0]=1;return a;}bigInt bigIntOrder(bigInt a){int i; ll k;REP(i,1,BIG_INT_SIZE) if(a.a[i-1]<0 || a.a[i-1]>=BIG_INT_BASE){k=a.a[i-1]/BIG_INT_BASE; a.a[i-1]-=k*BIG_INT_BASE;if(a.a[i-1]<0) k--, a.a[i-1]+=BIG_INT_BASE; a.a[i]+=k;}if(a.a[BIG_INT_SIZE-1]<0){rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i]; a=bigIntOrder(a);rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i];}return a;}bigInt llToBigInt(ll a){bigInt c; int i;REP(i,1,BIG_INT_SIZE) c.a[i]=0; c.a[0]=a;return bigIntOrder(c);}int bigIntGreaterThan(bigInt a,bigInt b){int i;for(i=BIG_INT_SIZE-1;i>=0;i--){if(a.a[i]>b.a[i]) return 1;if(a.a[i]<b.a[i]) return 0;}return 0;}int bigIntIsZero(bigInt a){int i; rep(i,BIG_INT_SIZE) if(a.a[i]) return 0; return 1;}bigInt bigIntPlus(bigInt a,bigInt b){int i; bigInt c;rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];return bigIntOrder(c);}bigInt bigIntMinus(bigInt a,bigInt b){int i; bigInt c;rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];return bigIntOrder(c);}bigInt bigIntMultipleLL(bigInt a,ll b){int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;return bigIntOrder(a);}bigInt bigIntPlusSimple(bigInt a,bigInt b){int i; bigInt c;rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];return c;}bigInt bigIntMinusSimple(bigInt a,bigInt b){int i; bigInt c;rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];return c;}bigInt bigIntMultipleLLSimple(bigInt a,ll b){int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;return a;}bigInt bigIntMultiple(bigInt a,bigInt b){int i,j,ii,jj; bigInt c;for(ii=BIG_INT_SIZE-1;ii;ii--) if(a.a[ii]) break; ii++;if(ii==1) return bigIntMultipleLL(b,a.a[0]);for(jj=BIG_INT_SIZE-1;jj;jj--) if(b.a[jj]) break; jj++;if(jj==1) return bigIntMultipleLL(a,b.a[0]);rep(i,BIG_INT_SIZE) c.a[i]=0;rep(i,ii)if(a.a[i])for(j=0;j<jj&&i+j+1<BIG_INT_SIZE;j++) c.a[i+j]+=a.a[i]*b.a[j];return bigIntOrder(c);}void bigIntDivisionsLL(bigInt a,ll b,bigInt *c,ll *d){int i;rep(i,BIG_INT_SIZE) c->a[i]=a.a[i];for(i=BIG_INT_SIZE-1;i;i--)c->a[i-1]+=(c->a[i]%b)*BIG_INT_BASE, c->a[i]/=b;*d = c->a[0]%b; c->a[0]/=b;}void bigIntDivisions(bigInt a,bigInt b,bigInt *c,bigInt *d){int i,j,s,sa,sb; ll ma,mb,mc; bigInt tmp;sa=bigIntSign(a); sb=bigIntSign(b);if(sa==-1) a=bigIntMultipleLL(a,-1);if(sb==-1) b=bigIntMultipleLL(b,-1);for(j=BIG_INT_SIZE-1;j;j--) if(b.a[j]) break;if(!j){REP(i,1,BIG_INT_SIZE) d->a[i]=0;bigIntDivisionsLL(a,b.a[0],c,&(d->a[0]));}else{for(i=BIG_INT_SIZE-1;i;i--) if(a.a[i]) break;s=i-j; if(s<0) s=0;rep(i,BIG_INT_SIZE) c->a[i]=0;while(s>=0){ma=0; mb=BIG_INT_BASE-1;while(ma!=mb){mc = (ma+mb)/2 + (ma+mb)%2;c->a[s]=mc; tmp=bigIntMultiple(*c,b);if(bigIntGreaterThan(tmp,a)) mb=mc-1; else ma=mc;}c->a[s]=ma; s--;}tmp = bigIntMultiple(b,*c);*d = bigIntMinus(a,tmp);}if(sa==-1 && sb==-1){*d=bigIntMultipleLL(*d,-1);} else if(sa==-1 && sb!=-1){*c=bigIntMultipleLL(*c,-1);*d=bigIntMultipleLL(*d,-1);} else if(sa!=-1 && sb==-1){*c=bigIntMultipleLL(*c,-1);}}bigInt bigIntDivision(bigInt a,bigInt b){bigInt c,d;bigIntDivisions(a,b,&c,&d);return c;}bigInt bigIntModular(bigInt a,bigInt b){bigInt c,d;bigIntDivisions(a,b,&c,&d);return d;}int bigIntSign(bigInt a){int i;for(i=BIG_INT_SIZE-1;i>=0;i--) if(a.a[i]){if(a.a[i]<0) return -1; else return 1;}return 0;}bigInt bigIntAbs(bigInt a){if(bigIntSign(a)==-1) return bigIntMultipleLL(a,-1LL); return a;}bigInt bigIntGCD(bigInt a,bigInt b){if(bigIntSign(a)==-1) a=bigIntMultipleLL(a,-1);if(bigIntSign(b)==-1) b=bigIntMultipleLL(b,-1);if(bigIntIsZero(a)) return b;return bigIntGCD(bigIntModular(b,a),a);}int bigIntToChar(bigInt a,char ret[]){int i,j,s=0,len=0; char ct[BIG_INT_CHAR_SIZE]; ll lt;if(bigIntSign(a)==-1){ret[0]='-'; len=bigIntToChar(bigIntMultipleLL(a,-1LL),ret+1); return len+1;}rep(i,BIG_INT_SIZE){lt=a.a[i]; rep(j,BIG_INT_DIGITS) ct[s++]=lt%10, lt/=10;}j=0;while(s--){if(ct[s]) j=1;if(j) ret[len++]=ct[s]+'0';}if(!len) ret[len++]='0';ret[len]='\0'; return len;}void printBigInt(bigInt a){int i,k; char tmp[BIG_INT_CHAR_SIZE];k=bigIntToChar(a,tmp); rep(i,k) putchar(tmp[i]);}void putBigInt(bigInt a){char tmp[BIG_INT_CHAR_SIZE];bigIntToChar(a,tmp); puts(tmp);}bigInt bigIntDivisionLL(bigInt a,ll b){bigInt res; ll tmp;bigIntDivisionsLL(a, b, &res, &tmp);return res;}bigInt bigIntSqrt(bigInt a){bigInt c1=bigIntZero(),c2=a,c,mul;while( bigIntGreaterThan(c2,c1) ){c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2);mul = bigIntMultiple(c,c);if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c;}return c1;}bigInt bigIntCubicRoot(bigInt a){bigInt c1=bigIntZero(),c2=a,c,mul;while( bigIntGreaterThan(c2,c1) ){c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2);mul = bigIntMultiple(c,bigIntMultiple(c,c));if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c;}return c1;}char memarr[17000000]; void *mem = memarr;#define MD 1000000007int N;map<ull,bigInt> mp[50][50];ull get_hash(vector<int> &v){int i;ull hs = 0;rep(i,v.size()) hs = hs * 8 + (v[i]+2);rep(i,v.size()) assert(v[i]+2 < 8);return hs;}int connect(vector<int> &v, int x, int y){int i, j, k, n = v.size();if(v[x]==-2 || v[y]==-2) return 0;if(v[x]==-1 && v[y]==-1){v[x] = v[y] = N+1;return 1;}if(v[x]==v[y]){v[x]=v[y]=-2;rep(i,n) if(v[i]>=0) return 0;return 2;}if(v[x]==-1 || v[y]==-1){if(v[x]==-1) v[x] = v[y], v[y] = -2;else v[y] = v[x], v[x] = -2;return 1;}j = v[x]; k = v[y];rep(i,n) if(v[i]==j) v[i] = k;v[x] = v[y] = -2;return 1;}int go[1000];int order(vector<int> &v){int i, j, k, n = v.size();k = 0;rep(i,n+3) go[i] = -1;rep(i,n){if(v[i]<0) continue;if(go[v[i]]==-1) go[v[i]] = k++;}rep(i,n){if(v[i]<0) continue;v[i] = go[v[i]];}return k;}bigInt solve(int a, int b, vector<int> mask){int i, j, k, m;int fin;ull hs;vector<int> send;bigInt res = bigIntZero(), tmp;if(a<b){while(b!=N){if(mask[0] >= 0) return bigIntZero();REP(i,1,mask.size()) mask[i-1] = mask[i];mask[mask.size()-1] = -1;b++;}}if(b==N) a++, b=0;if(a==N) return bigIntZero();hs = get_hash(mask);if(mp[a][b].count(hs)) return mp[a][b][hs];rep(m,7){send = mask;fin = 0;if(m&1<<0){if(a < b) continue;if(b-1 < 0) continue;if(fin) continue;k = connect(send, N+1, N);if(k==0) continue;if(k==2) fin=1;order(send);}if(m&1<<1){if(a < b) continue;if(a-1 < 0 || a-1 < b) continue;if(fin) continue;k = connect(send, N+1, 1);if(k==0) continue;if(k==2) fin=1;order(send);}if(m&1<<2){if(a < b) continue;if(a-1 < 0 || b-1 < 0) continue;if(fin) continue;k = connect(send, N+1, 0);if(k==0) continue;if(k==2) fin=1;order(send);}if(fin){ res = bigIntPlus(res, bigIntOne()); continue; }if(send[0] >= 0) continue;REP(i,1,send.size()) send[i-1] = send[i];send[send.size()-1] = -1;tmp = solve(a,b+1,send);res = bigIntPlus(res, tmp);// printf("%d %d :",a,b);// rep(i,mask.size()) printf(" %d",mask[i]);// printf(" -> ");// printf("%d %d :",a,b+1);// rep(i,mask.size()) printf(" %d",send[i]);// puts("");}// printf("%d %d :",a,b);// rep(i,mask.size()) printf(" %d",mask[i]);// printf(" : %lld\n", res);return mp[a][b][hs] = res;}int main(){int i, j, k;bigInt res;vector<int> tmp;for(N=2;N<=13;N++){rep(i,N+1) rep(j,N+1) mp[i][j].clear();tmp.clear();tmp = vector<int>(N+2,-1);// rep(i,N+2) tmp.push_back(-1);res = solve(0,0,tmp);printf("%d ",N);putBigInt(res);}puts("OK");return 0;}*/// 2 1// 3 11// 4 110// 5 2402// 6 128967// 7 16767653// 8 5436906668// 9 4406952731948// 10 8819634719356421// 11 43329348004927734247// 12 522235268182347360718818// 13 15436131339319739257518081878const char *ans[] = {"0","1","11","110","2402","128967","16767653","5436906668","4406952731948","8819634719356421","43329348004927734247","522235268182347360718818","15436131339319739257518081878"};int main(){int N;reader(&N);writerLn(ans[N]);return 0;}