Advertisement
Guest User

Untitled

a guest
Oct 8th, 2014
618
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.62 KB | None | 0 0
  1. /*
  2. Author      : Rashedul Hasan Rijul ( Silent_coder ).
  3. Created on  : 2014-10-08
  4. */
  5.  
  6. #pragma warning (disable: 4786)
  7. #pragma comment (linker, "/STACK:0x800000")
  8.  
  9. #include<stdio.h>
  10. #include<string.h>
  11. #include<math.h>
  12. #include<stdlib.h>
  13. #include<ctype.h>
  14. #include<iostream>
  15. #include<algorithm>
  16. #include<vector>
  17. #include<string>
  18. #include<queue>
  19. #include<stack>
  20. #include<map>
  21. #include<set>
  22. using namespace std;
  23.  
  24. #define maxm 1010
  25. #define inf (1<<29)
  26. #define ii __int64
  27.  
  28. #define pi  acos(-1.0)
  29. #define eps 1e-9
  30. #define iseq(a,b) (fabs(a-b)<eps)
  31.  
  32. #define pii pair<int,int>
  33. #define mp  make_pair
  34. #define uu first
  35. #define vv second
  36.  
  37. ii on(ii n,ii k){ return (n|(1<<k)); }
  38. ii off(ii n,ii k){ return (n-(n&(1<<k))); }
  39. bool chck(ii n,ii k){ return (n&(1<<k)); }
  40.  
  41. ii mini(ii a,ii b){ if(a<b) return a;  return b;  }
  42. ii maxi(ii a,ii b){ if(a>b) return a;  return b;  }
  43.  
  44.  
  45. int n,m;
  46. int sld[5][maxm];
  47. ii req;
  48. ii req_arr[maxm];
  49. ii arr[maxm];
  50.  
  51. ////////////*********  Trie + Aho Corasick  ********/////////////////
  52.  
  53. //  maxn =required trie  node ....
  54. #define maxn 1000100
  55.  
  56. struct trie{
  57.     int ind;
  58.     map<ii,int>edges;
  59. };
  60. trie Tri[maxn],root;
  61. int tot,f[maxn],pos[maxn],kas=1; //  f=failure....
  62.  
  63.  
  64. void init(trie *a,int ind){
  65.     a->ind=ind;
  66.     a->edges.clear();
  67. }
  68.  
  69. void add(trie *a,ii arr[],int ind){
  70.  
  71.     int i,l,id;
  72.  
  73.     for(i=1;i<=n;i++){
  74.         id=arr[i];
  75.         if(a->edges.find(id)==a->edges.end()){
  76.             a->edges[id]=tot;
  77.             init(&Tri[a->edges[id]],tot++);
  78.         }
  79.         a=&Tri[a->edges[id]];
  80.         if(i==n){
  81.             pos[a->ind]=kas;
  82.             continue;
  83.         }
  84.     }
  85.  
  86. }
  87. void build(){
  88.  
  89.     int i,j,piv;
  90.     trie *a=&Tri[0];
  91.  
  92.  
  93.     //  Failure  Function .........
  94.  
  95.     queue<int>q;
  96.  
  97.     map<ii,int>::iterator it;
  98.  
  99.     for(it=a->edges.begin();it!=a->edges.end();it++){
  100.         f[it->vv]=0;
  101.         q.push(it->vv);
  102.     }
  103.  
  104.     while(!q.empty()){
  105.  
  106.         int state=q.front(); q.pop();
  107.  
  108.         a=&Tri[state];
  109.         for(it=a->edges.begin();it!=a->edges.end();it++){
  110.             int failure=f[state];
  111.             while(failure && Tri[failure].edges.find(it->uu)==Tri[failure].edges.end()){
  112.                 failure=f[failure];
  113.             }
  114.             if(failure) failure=Tri[failure].edges[it->uu];
  115.             piv=Tri[state].edges[it->uu];
  116.             f[piv]=failure;
  117.  
  118.             q.push(piv);
  119.         }
  120.     }
  121. }
  122.  
  123.  
  124.  
  125.  
  126. int find_next(int curr,int id){
  127.  
  128.     //printf("curr =%d %c-%d\n",curr,ch,id);
  129.     while(curr && Tri[curr].edges.find(id)==Tri[curr].edges.end()) curr=f[curr];
  130.     //printf("curr =%d %c-%d %d\n",curr,ch,id,Tri[curr].edges[id]);
  131.     if(Tri[curr].edges.find(id)==Tri[curr].edges.end()) return 0;
  132.     return Tri[curr].edges[id];
  133. }
  134.  
  135. int match(ii a[]){
  136.  
  137.     int i,j,l;
  138.  
  139.  
  140.     int curr=0;
  141.     for(i=1;i<=n+n;i++){
  142.         curr=find_next(curr,a[i]);
  143.         if(pos[curr]==kas) return 1;
  144.     }
  145.  
  146.     if(pos[curr]==kas) return 1;
  147.     return 0;
  148. }
  149.  
  150.  
  151. //////////////////**************   END       *****************////////////////
  152.  
  153. void print(int a[]){
  154.  
  155.     for(int i=1;i<=n;i++){
  156.         printf("%d ",a[i]);
  157.     }
  158.     puts("");
  159. }
  160.  
  161. int main(){
  162.  
  163.     int i,j,k,l,test,t=1;
  164.  
  165.     //freopen("in.txt","r",stdin);
  166.     //freopen("out.txt","w",stdout);
  167.  
  168.     scanf("%d",&test);
  169.  
  170.     while(test--){
  171.  
  172.         //Init.......
  173.         kas++;
  174.         tot=0;
  175.         root=Tri[0];
  176.         init(&Tri[0],tot++);
  177.  
  178.         scanf("%d",&n);
  179.  
  180.         ii sum=0;
  181.         for(j=1;j<=4;j++){
  182.             for(i=1;i<=n;i++){
  183.                 scanf("%d",&sld[j][i]);
  184.                 sum+=sld[j][i];
  185.             }
  186.         }
  187.  
  188.         req=sum/(ii)n;
  189.  
  190.         printf("Case %d: ",t++);
  191.  
  192.         if(req*n!=sum){
  193.             puts("No");
  194.             continue;
  195.         }
  196.  
  197.         for(i=1;i<=n;i++){
  198.             req_arr[i]=req-sld[4][i];
  199.         }
  200.  
  201.         for(i=1;i<=n;i++){
  202.             for(j=1,k=i;j<=n;j++,k++){
  203.                 if(k>n) k=1;
  204.                 arr[j]=req_arr[j]-sld[3][k];
  205.                 if(arr[j]<0){
  206.                     break;
  207.                 }
  208.             }
  209.             //print(arr);
  210.             if(j<=n) continue;
  211.             add(&Tri[0],arr,i);
  212.         }
  213.  
  214.         build();
  215.  
  216.         //puts("match");
  217.         for(i=1;i<=n;i++){
  218.             for(j=1,k=i;j<=n;j++,k++){
  219.                 if(k>n) k=1;
  220.                 arr[j]=sld[2][j]+sld[1][k];
  221.             }
  222.             for(j=1;j<=n;j++){
  223.                 arr[n+j]=arr[j];
  224.             }
  225.             //print(arr);
  226.             if(match(arr)) break;
  227.         }
  228.  
  229.         if(i<=n){
  230.             puts("Yes");
  231.         }
  232.         else{
  233.             puts("No");
  234.         }
  235.  
  236.     }
  237.  
  238.     return 0;
  239. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement