2010-02-17
TLE
|http://felicity.iiit.ac.in/tle/
全問解いて19位はちょっと恥ずかしいので来年に向けて色々頑張りたい
PALIN1 (Super Palindrome - 1; 問題文): 58.7356 / 100
- n^n%p。要128bit演算
/*// /*/typedef long long l;l n,p,u=1<<30,c,d;l j(l x,l e){return--e?j(x*4%p,e):x;}l m(l a,l b){c=a%u,a/=u,d=b%u,b/=u;return(j(a*b%p,31)+j((a*d+b*c)%p,16)+c*d%p)%p;}l f(l a,l b){return b?b&1?m(a,f(a,b-1)):f(m(a,a),b/2):1;}main(t){scanf("%d",&t);while(t--)scanf("%lld%lld",&n,&p),printf("%lld\n",f(n,n));}//*// /*/typedef long long l;l n,p,u=1<<30,c,d;l j(l x,l e){return--e?j(x*4%p,e):x;}l m(l a,l b){c=a%u,a/=u,d=b%u,b/=u;return(j(a*b%p,31)+j((a*d+b*c)%p,16)+c*d%p)%p;}l f(l a,l b){return b?b&1?m(a,f(a,b-1)):f(m(a,a),b/2):1;}main(t){scanf("%d",&t);while(t--)scanf("%lld%lld",&n,&p),printf("%lld\n",f(n,n));};;};))n,n(f,"n\dll%"(ftnirp,)p&,n&,"dll%dll%"(fnacs)--t(elihw;)t&,"d%"(fnacs{)t(niam};1:)2/b,)a,a(m(f:))1-b,a(f,a(m?1&b?b nruter{)b l,a l(f l};p%)p%d*c+)61,p%)c*b+d*a((j+)13,p%b*a(j(nruter;u=/b,u%b=d,u=/a,u%a=c{)b l,a l(m l};x:)e,p%4*x(j?e--nruter{)e l,x l(j l;d,c,03<<1=u,p,n l;l gnol gnol fedepyt/*/ //*//
- /...// で囲むだけで十分
PALIN2 (Super Palindrome - 2; 問題文): 111.6 / 150
- これは簡易版
/*/i,x,n,p;main(t){scanf("%d",&t);while(t--){scanf("%d%d",&n,&p);i=x=1;while(i++<=n)x=(long long)x*n%p;printf("%d\n",x);}} ///*/i,x,n,p;main(t){scanf("%d",&t);while(t--){scanf("%d%d",&n,&p);i=x=1;while(i++<=n)x=(long long)x*n%p;printf("%d\n",x);}} ///*/i,x,n,p;main(t){scanf("%d",&t);while(t--){scanf("%d%d",&n,&p);i=x=1;while(i++<=n)x=(long long)x*n%p;printf("%d\n",x);}} //
- 最後に//を置くだけでいいじゃん
PREP (The Preprocessor Problem; 問題文): 5.6684 / 100
- これは浜地さんの出題だそうです。
- cpp(プリプロセッサ)でfizzbuzz。あとでじっくり考えたい
#define X F B #define F Fizz #define B Buzz 1 2 F 4 B F 7 8 F B (以下省略)
CARM (Carmichael Numbers; 問題文): 3.2305 / 100
- 自作Bignumが遅くてTLE(文字通りの)との闘い
#include <vector> #include <set> #include <string> #include <stack> #include <sstream> #include <iostream> #include <cstdlib> using namespace std; typedef long long LL; LL random(LL n){return (LL)rand()%n;} LL c1(LL m,LL a){LL r=a*a%m;return(1LL<a&&a<m-1&&r==1)?0:r;} LL expmod(LL base,LL exp,LL m){if(!exp)return 1;else if(!(exp&1))return c1(m,expmod(base,exp/2,m));else return base*expmod(base,exp-1,m)%m;} bool mr(LL n){return expmod((1LL+random(n-1)),n-1,n)==1;} bool pq(LL n,int times=4){ if(n==1)return false; if(n==2)return true; else if(!(n&1))return false; for(int i=times;i>0;i--)if(!mr(n))return false; return true;} class Bn { int sign; int size; vector<LL> values; int remainder_; public: Bn(int val=0){set(val);} Bn(const Bn& num){set(num);} void set(int val); void set(const Bn& num); private: bool is_zero() const { return (size==1 && values[0]==0)? true : false; }; void normalize(); char enc(int n) const { return n<10 ? '0'+n : 'A'+(n-10); } int dec(int ch) const { return ch<='9' ? ch-'0' : 10+ch-'A'; } public: Bn abs() const; int cmp(const Bn &n) const; int cmp_abs(const Bn &n) const; int to_i(); string to_s() const; void operator*=(int n); void operator/=(int n); int remainder(){ return remainder_; } }; void Bn::set(int val){ sign = 1; if (val >= 65536) { values.resize(size = 2); values[0] = val % 65536; values[1] = val >> 16; } else { values.resize(size = 1); values[0] = val; } } void Bn::set(const Bn& num){ values.assign(num.values.begin(), num.values.end()); sign = num.sign; size = num.size; } int Bn::to_i() { switch(size){ case 1: return sign * values[0]; case 2: if (values[1]<=0x7fff) return sign * ((values[1]<<16) | values[0]); else ; default: return 0; // NaN } } int Bn::cmp(const Bn &n) const { if(sign != n.sign) return (sign - n.sign)/2; return sign * cmp_abs(n); } int Bn::cmp_abs(const Bn &n) const { if(size!=n.size) return size - n.size; for(int i=size-1;i>=0;i--) if(values[i]!=n.values[i]) return values[i] - n.values[i]; return 0; } void Bn::operator*=(int n){ for(int i=0;i<size;i++) values[i]*=n; normalize(); } void Bn::operator/=(int n){ int r = 0; for(int i=size-1; i>=0; i--){ int v = (r << 16) + values[i]; r = v % n; values[i] = v / n; } normalize(); remainder_ = r; } void Bn::normalize(){ unsigned int overflown=0; int sz=1; for(int i=0;i<size;i++){ if (values[i]>0) sz=i+1; if (values[i]<0) { if (i==size-1) { sign=-sign; values[i]=-values[i]; for (int j=i-1;j>=0;j--){ } } else { // borrowable int b=-values[i]; values[i+1] -= (b >> 16); if (b&0xffff){ values[i+1]--; values[i] = 65536 - b; } else { values[i] = 0; } } } if (values[i]>=65536){ if (i==size-1) overflown = values[i] >> 16; else values[i+1] += values[i] >> 16; values[i] %= 65536; } } if (overflown == 0) { if (sz<size) values.resize(size=sz); if (is_zero()) sign=1; } else if (overflown < 65536){ values.resize(size+1); values[size++] = overflown; } else { values.resize(size+2); values[size++] = overflown % 65536; values[size++] = overflown >> 16; } } string Bn::to_s() const { if (is_zero()) return "0"; stack<char> s; Bn tmp(*this); while(!tmp.is_zero()){ tmp /= 10; s.push(enc(tmp.remainder())); } stringstream ss; if (sign == -1) ss << "-"; while(!s.empty()){ ss << s.top(); s.pop(); } return ss.str(); } int main(){ int L=6400; LL a,b,c,x,k; cout << L << endl; x=0; for(k=1;;k++){ a=6*k+1;if(pq(a)){ b=a*2-1;if(pq(b)){ c=a+b-1;if(pq(c)){ Bn z(1); z*=a;z*=b;z*=c; cout << z.to_s() << endl; cout << 3 << " " << a << " " << b << " " << c << endl; x++; if (x==L) break; } } } } return 0; }
COMP (Compress the Text/Image; 問題文): 76.973 / 100
- tsubosakaさんさすがと思った
j,h,l;r(c){putchar("\n (),-.12356789:=ABCILMOSTYabcdefghijklmnopqrstuvwxyz"[c&63]);}q(x,n){r(x>>18);if(n>1)r(x>>12);if(n>2)r(x>>6);if(n>3)r(x);}p(unsigned char*b,int n,int m){for(h=0;h<m;n-=4,h+=3)q(b[h]<<16|b[h+1]<<8|b[h+2],n);}main(i){p("E��P���a�����^~���v*#���&��=�i���~�A�����~���:h��h�;n�`�ݺ���}���a~蟰,�pn��N(����rg�\n)�����`r\rbn�ݹ�-�����'�E��P.n����`������Q@]�z���.؛��n~�m~�A�;��)��߹�3�~��xbn�ݹ�-'Κ�r\r؛��n~�A��m��nǁ0W#�XMEb|��pc�涐f��_�0o��l~��A����}�[��c�_���`Qa5�.����v�۹��;��3��ގ�l�x��.~�o���;�|X)�pfn�on����_ɹ��A��Qa5�.��;�`�'� `���\n�h�)��.���)��Dh�|h�n����:hn`nΧ�;��0m�n�S��#~�`��j��_��z��'����۶�-Q@[��qn�\\��ŻAq�[���}�&�������i���fݕ���7m�#�;��说bn�ݹ�-�|�}�c��m���a�����gn�mf����gn�Az<#�:h��ߠ���~�����)r�`���z8 ~���~�D��������i����_xXMEnˁ��j�:.f��\\n�����c�n��^�펚}�c~�n�j��m��n�n��l~���]�������l��x3�]�z������n�l�vg�`Qa5�.�����}�c�۲l�|Yێ`q���v�~�]���n��~wy����۾��`_ɹ��i�XMEFˁ<�� Qa5.���춚��c��|n�����5",1227,921);unsigned char d[]="��������������������������������a�����������a�e�a��������a�a�a�d�g������������a�b�m����������a������%B��o����A��A�����A$�!C����q�������A�A�!C�A�A�!�!�\042�\042�\042A����s������C!�!�!�������\042�!A��t����A���A!�!���������A!A��t����A�������������#A��i�k���������B�!���������!�A!A��w���A�B�F\042�������!�!�!A��a�s���C*�!���������!�!�B��t���A\042�!���!���!�!�B��s���!�����\042�\042���!��i���B�!�����!�\042�������āA���f�����\042�!�����������!�!�����A!I��c��A����A!���������������������!A���B��b��A��A!A�����������\042���!�����!A�a�c��B���B��a�A�!�!���!����#�������!��!��f��A���B��A��!�����������!�\042�����!�����A��!�f�B���B����!�!�������������������!����A�d�B���B����A�!�������!�����������!���!���!Á�a�b�B��B��A!�!�!����!��$����������������¡e�B�a��A��B�A\042���!�����������������!�b��A��b�A��A�A!�A���!�����������!�!�����A�a��A��c���!�A�!��������\042������!��!�!�!�\042���!ȁ��A��e��\042B\042�������������!�!�\042���!C��f���A��!�����!�������#��!�!A��g��!A!�!�����\042�!�������!�!�!�!��!�!Ł�h���!�B!���!�!�$A�!�������!�!���!�!�!�h���B#���'A)��!�!�!�A�f��A�A�����!�+D!C#�����\042�!�\042��f��!��!�����!�&C�F�F!����������!�\042�!��a�\042�B���&D�C!����������#�\042A���a��!���&C�A�����������!�!��\042���a�a�¡�!���%B�A!����������!���!A�!�\042���a�!�A!����\042�!D�A������������\042�\042�A�a����!���\042E�A�������\042���\042�\042A�A���!A�A���!A!D�A��������������\042���%�!�A!B����B�A���#F���A�������!���\042���!�!�A\042A����������!A!E���A�!�������������!�#�!�#���!A����#F�����������A�!��������#���\042�!�!�#����B���\042E��������������#���%�#����!������#E�������!�!�����\042��!�#�\042A��A!A!�����#E�����A�!�����!�������!���!�#��#����!����#D����������\042�����!���%�\042A���B�����#D������!�����A�!�\042��#��!�����!A!C����\042�!���!�!�!�!A!�\042��A\042��#D���!�!�������!�!�#�\042���A!��\042E��A�!�!���!�!�#�\042��\042����!F����#�����A�!�!�a���!���!E����\042A!�!�!�!�!��!�\042�!��A���!F����b��\042�!�A�!�!�!�!�!�!���\042���\042F��a�b��A�A�A�����!���\042�!����!���\042E��d��!�\042A!�#����!���\042F��b�a��A$A�!�!�!�!��a��A�����\042E��a�a�a��B#A���!�!�\042�!�!���A�����#E��e�a��$A\042�!���!�\042�#���!�����#D��a�b���\042�!A�!�����A!�!�!��A�A�����#C��a�b�c�B�#�!�!�!�&���A���\042C��a�a�g��A!�\042�!�!���#�!A�!���!����#C��c�j�\042�!A!�!�\042�!�A��a�!���#C�A��g�j��A#A!�!���\042�$A�!���!���#G��d�a�a�fb��%���#�B��a��!���#A�\042A��d�hd���!A$���!�\042�\042A!��!A���#�!A��c�m���&�����$��A!�!���#�A��a�a�g��B\042�\042A!�����!�!�A\042��A\042�!���!�!B�A\042�\042�\042�����A\042�!�#A�\042�A�!���!�!�!�!�$��!B�\042��\042�!A�A�\042A���A�%�!�!���!�!�!�!�!A���B!�!�A��\042�A�A!�!A���!�A!A�\042A!�#�!�!�!�!�!��!�!�!�!A�#��a�A\042A�!�!���!B�A!�!A���A!A\042A!�!�\042��A\042A!�!�!�!�!�!�#�!�\042��C!�!�!�\042���#C�A�C$���B%B����$�\042�\042�!���#�!�\042����A!�!�A!���#E!B!D�D\042���E��#�!�!�\042�#���!�A�%���#D!�\042�!B�F���\042�!�!�!�#�\042�!�\042�\042��A�A�!�$���$�\042���!�!A�E���E\042�B�#A!�\042�\042�\042�!�\042�$�!�!���A�A\042�!�\042���\042�!�����!A�D���C#�#�\042�\042�A�\042�#��!�\042�!����B�!�!A���#�A\042�%A�B�A��b��!�\042�!�\042�!�\042�!�\042�!���!���!�A%�!���!C\042�A#�B��!A�A��a��A�!�$B!�!�\042�\042�A\042�!�\042�!�!��A!B'��\042B�A!�#C�B�A��b����A�A�A!�\042B�\042�#�$�!�#�!���!��D!�\042A!�!��\042B�B�\042A\042B�A��b�����C��B\042B��!�!�!�!A\042�!�#�A�!��!A�\042�!�!�\042A�B\042�#�A���A�����A�B�F��!�!A�$�!�!�!�\042��!�!�\042�!��\042A�B!D�������C#�$�!�\042�!�!�\042�!��!A�!�#��!B�D�������A\042C!B�!A�!�!�\042�!A����!�A�%����\042A�������A�A�A�A!�!�!�\042�!�!�\042�A����!�A�!�\042��!B�������A�A��!�A�!A�A����C�#����!B�������������!A�\042�����B�#����!B������������%�!�!�����\042�\042����\042B�����������!�\042�\042�\042����A!�\042������!C������������A���!�\042�A!�!�A����A!�!�!����!C�������������!�\042�\042�!�A!��\042�\042��!C���A����a���!���%�\042�!A��A!�A��!C�����A����a�b���������%�#A����!���!�!��!D������a�a�b���!���������#A!�%�!���!�#�����!C������c�b�a���������������\042�!A�\042B!�!����!�A!���!C������a�e��!���������A�!�#A!�\042���A#�!A!���!B��������b�c�b��A�����#�!�\042A!�\042�����A�!�\042����!C������a�a�a�c�a��A���!�A#�\042�\042A���A!�!A!����!C������a�c��A���!�$�A\042�!A���A�\042�!�����C����a���a�d��A���!�!�A\042�\042A�����A�#�!��\042C���B����a��A���\042�B�$��A��A�\042�\042�����!C���B��������\042�A#A!�!�!���%�����!C���A�A���C!A�����A���!A\042�!�A����!�%�����!B���D�A�������B����!A!�!��A���!�#�!����!C���E�����C���A#���A�����!�!�!����!�\042C���A��a��B!������!�!���!���!�#�!�!�����!�\042B�A�����D����!�!���\042��!�\042�!�!A���!��!E�����D!���!�\042���!�\042��A!�\042C���D!A�������!��\042�!����%�!�!���!��A!D�����F!�������!���A!�!���A!�\042���!���A�#D�E���D�B!A���!�!�\042���\042�!�!��!A!C�A!F���A���F!�����%��\042�!���!�A\042D�A\042G�A�A�����C\042���!���!A\042����#�!�!�\042C�B#J�A�B�������E!���!���!A!����\042���\042A�!E�B#C\042M�C�����D\042�����\042A!�����\042���A�!�D�A%A����B�B!F���C\042�����\042A!���\042���\042�\042C�D��b��\042F���A�C!�������!A\042����A\042���A�\042C�G��a�a��G���D\042�����!A\042���!�������#C�J�B�C�B�������D!�����#���!���!�!C�A!C�����D\042�!�����!A!���!�����!�!C�E�����A���B#�!���\042���!�����!�!C�A!C���a����B�����B#�\042�����#���A���������D�A!C���D���B\042�A!��\042���!�!���!��������!C�B!C�F���D!�B!���A�����$���!������A���C�C\042G���A\042�!B���!A�������$�����������!C��B\042�!�A!�������%��������\042A�!B��B\042�A�A!�����������\042�!������!����C�������B\042�A�B!�������$��������!C�����A!�A�C!�������A\042������������!B���B!�A�A\042�������$�!������!����C���C�A�B\042���$���!��������!B���B!ÅA!A!�����%�A���������!A���B!ÆB!�����%�A�������������B�����C�!�E\042�!���$A��A��������A��!��B�����C!�!�C\042�!�!�����\042B��A����������!aA���\042B�C\042��A�C\042�#�����%�!������A���#A�D!�!A�D\042�!A!�!�������#�!����!���Á�!����!A�!C�C!���!A�A�C!�\042A�!���!���%�����!���!A���!�A����!B�D�C!���!B���A!�\042���\042�!�!�!��A����!�!���Á!�A����C��!J�B\042�!C�A�!���\042A!�!�$������A�����!�B��D!���#J!�!A�!���\042A\042�!�!�������A�����A��D�!���!A�C�A����!A!�A\042�\042��!������������������!C�B!�\042A�A�A���A!B�\042����!����������!����!C�K������!�A!A#�!��A\042��������A����A����D�B������A!����!�A%�!��#�������A����������!C�����!�!��!��!�A#���A#������!���\042����#C������������!�������!�$���A!A!����������#D���������!����!�!���!B�����������#D��A�����!��!����!�!�A#����������$D���A���������!������C!�����������#E���A����!���A����!��D������!A�����#C�A���������A�����C�!������A�������#C�A�!����������������D���������#D�A���������������!�A!���������\042�\042C�A�A���������������A!B�������&C�A�B��������������A!�A���������\042A!D�A�����������������A�A�����������#A\042D�A�!����!���������C!���������$F�������!�!�����!�����C�����������$A!D������������\042�!���������A!���������������!A!C!B�������A���'�!�\042�������A\042�����������\042��$E�����!����&�!�!�!�����B!������\042���A!G����������%�#�\042�����A!�������!����#���\042C�A!A���������A���!�#A!�!�#�!�����A!�����������#���!B�B�����A���\042�\042A#�\042B�!���!���A!���������$�\042����D�B���������A���A!�!�!A#�\042A!�!�����A!�����!�!�#���D�A�����B���%�%�!B�����!�������!�\042B!��!C�A�����A!���A%�%�!A\042�����!�����!E��D�A�����A!���A$A!�B\042�$��!��B!������!�\042E��!A�A�������A���\042A!B!���!A�!�#����B�������!�#D!���!A�A�����!���'�\042�!�!����������B�������!���\042E!�A�A������\042A!A!�\042�������������A���������!�\042F!ȆA�A���!���!B!A!�������������B���!��!�!�#D#���A�A������A���!A!A!�!���������C#B\042�\042��!��\042�#E\042���!A�A���A���!A!�!�!�������#A�B\042A!�#C��A��#�\042E\042���B�A�a������A!������!���&G#A!A!��!�\042E!���!D�A�������B����\042���������E!G'�!�!�A!�!A%���!C�A���B!���������F�'���(�#A\042��\042A�!���������A�B�B\042������������B�C���G!��%�\042�#���\042E�B�������D#A\042��������A�C���A�A�D��+�����%�C�A���C!A$A�!�������B�A���A�A!�!�!A!E!B\042�����!�!F���H\042�#�����D�A����B�C��!M\042���!J���B�C(�\042��������E�D�A����!Q!��!H�B�A�F%B)�������A�D����!��!R���D�C�A�D�C#I!���E���a�A!�A��F�H�B���E�A�C�D�C!�!�����!�!�E�����A!��!M�A��\042�!C��A�C!�!�������!A%�E��A�C�D�!M�B��\042A�����B!�#���!A#A�E��A�J!��I�A�A�!��$�A�����A�A�#���!�%A!�E����M�!I�A�A�!��\042�A�����C�$�����%�!A��E���M!�!G�B����!�B�A��B!�#�����#A\042��E���N���!I����!�C���A��A\042�#���#A\042A�E�O��$F�A����!�!A�A���C!�\042���!A!A\042��E��O�\042A\042F�A��!�A�A�B�����B!�!A���$A\042�B�A��O!�!��A\042F�C�āA�A�����B\042�!A!�����#A!A����";for(i=0;i<sizeof(d);i++){h=d[i]>>5,l=d[i]&31;if(h)for(j=0;j<l;j++)putchar("_#*.+:@W"[h]);else if(l>15)for(j=16;j++<l;)putchar(',');else putchar(10);}p("�AΛ�������m�z�|`Z��d�ہ����A���n�;An����o����mv����c�`[������<���mv���P%_���Λ��f���1�",172,129);}
SHORTEN (Play with Code; 問題文): 18.2888 / 100
- コードちゃんと読んでないので時間あればもっと取れた
#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct B{int o,c;struct B*l,*r;}S;S*at,A[200000];void F(S*s,char*w,int l){if(l==0)return;if(l==1){s->o=(*w=='(');s->c=(*w==')');s->r=s->l=NULL;return;}s->l=at++,s->r=at++;F(s->l,w,l/2);F(s->r,w+l/2,l-l/2);S*L=s->l,*R=s->r;if(L->o>=R->c)s->o=L->o+R->o-R->c,s->c=L->c;else s->o=R->o,s->c=R->c+L->c-L->o;}void G(S*s,char k,int l,int i){if(!(s->l||s->r)){if(k=='(')s->o++,s->c--;else s->o--,s->c++;return;}if(i<l/2)G(s->l,k,l/2,i);else G(s->r,k,l-l/2,i-l/2);S*L=s->l,*R=s->r;if(L->o>=R->c)s->o=L->o+R->o-R->c,s->c=L->c;else s->o=R->o,s->c=L->c+R->c-L->o;}int main(){int T;scanf("%d",&T);while(T--){printf("%d:\n",10-T);char w[40000];int l;scanf("%d%s",&l,w);at=A+1;S*s=A;memset(s,0,sizeof(A));F(s,w,l);int M;scanf("%d\n",&M);while(M--){char v[11];gets(v);int k=atoi(v)-1;if(k<0)printf("%s\n",s->o||s->c?"NO":"YES");else{w[k]=w[k]=='('?')':'(';G(s,w[k],l,k);}}}return 0;}
KEY (Key to C; 問題文): 69.4118 / 100
- 問題の意味がわからず悩んだ
n,p,z,x,e;r(w,y,i){i?r(w/2,y*2+w%2,i-1):(e=y);}main(t){scanf("%d",&t),f(t);}f(t){t&&(scanf("%d%d",&n,&p),g(z=0),printf("%d\n",z),f(t-1));}g(x){r(x,0,32),x<=n&&(!(~n&x)&&__builtin_popcount(x^e)<=p&&z++,g(x+1));}
CQUINE (Chain Quine!; 問題文): 94.2466 / 200
- quineが書けただけで満足っす
char*s="char*s=%c%s%c,q=34,y=92;n,j;k(x){return x-n?x<n?k(x*2):j?x:x/2:x;}main(t){j=%d;scanf(%c%%d%c,&t);while(t--){scanf(%c%%d%c,&n);n>0?printf(%c%%d%cn%c,k(1)):printf(s,q,s,q,1-j,q,q,q,q,q,y,q);}}",q=34,y=92;n,j;k(x){return x-n?x<n?k(x*2):j?x:x/2:x;}main(t){j=1;scanf("%d",&t);while(t--){scanf("%d",&n);n>0?printf("%d\n",k(1)):printf(s,q,s,q,1-j,q,q,q,q,q,y,q);}}