Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : Rashedul Hasan Rijul ( Silent_coder ).
- Created on : 2014-10-08
- */
- #pragma warning (disable: 4786)
- #pragma comment (linker, "/STACK:0x800000")
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<stdlib.h>
- #include<ctype.h>
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<string>
- #include<queue>
- #include<stack>
- #include<map>
- #include<set>
- using namespace std;
- #define maxm 1010
- #define inf (1<<29)
- #define ii __int64
- #define pi acos(-1.0)
- #define eps 1e-9
- #define iseq(a,b) (fabs(a-b)<eps)
- #define pii pair<int,int>
- #define mp make_pair
- #define uu first
- #define vv second
- ii on(ii n,ii k){ return (n|(1<<k)); }
- ii off(ii n,ii k){ return (n-(n&(1<<k))); }
- bool chck(ii n,ii k){ return (n&(1<<k)); }
- ii mini(ii a,ii b){ if(a<b) return a; return b; }
- ii maxi(ii a,ii b){ if(a>b) return a; return b; }
- int n,m;
- int sld[5][maxm];
- ii req;
- ii req_arr[maxm];
- ii arr[maxm];
- ////////////********* Trie + Aho Corasick ********/////////////////
- // maxn =required trie node ....
- #define maxn 1000100
- struct trie{
- int ind;
- map<ii,int>edges;
- };
- trie Tri[maxn],root;
- int tot,f[maxn],pos[maxn],kas=1; // f=failure....
- void init(trie *a,int ind){
- a->ind=ind;
- a->edges.clear();
- }
- void add(trie *a,ii arr[],int ind){
- int i,l,id;
- for(i=1;i<=n;i++){
- id=arr[i];
- if(a->edges.find(id)==a->edges.end()){
- a->edges[id]=tot;
- init(&Tri[a->edges[id]],tot++);
- }
- a=&Tri[a->edges[id]];
- if(i==n){
- pos[a->ind]=kas;
- continue;
- }
- }
- }
- void build(){
- int i,j,piv;
- trie *a=&Tri[0];
- // Failure Function .........
- queue<int>q;
- map<ii,int>::iterator it;
- for(it=a->edges.begin();it!=a->edges.end();it++){
- f[it->vv]=0;
- q.push(it->vv);
- }
- while(!q.empty()){
- int state=q.front(); q.pop();
- a=&Tri[state];
- for(it=a->edges.begin();it!=a->edges.end();it++){
- int failure=f[state];
- while(failure && Tri[failure].edges.find(it->uu)==Tri[failure].edges.end()){
- failure=f[failure];
- }
- if(failure) failure=Tri[failure].edges[it->uu];
- piv=Tri[state].edges[it->uu];
- f[piv]=failure;
- q.push(piv);
- }
- }
- }
- int find_next(int curr,int id){
- //printf("curr =%d %c-%d\n",curr,ch,id);
- while(curr && Tri[curr].edges.find(id)==Tri[curr].edges.end()) curr=f[curr];
- //printf("curr =%d %c-%d %d\n",curr,ch,id,Tri[curr].edges[id]);
- if(Tri[curr].edges.find(id)==Tri[curr].edges.end()) return 0;
- return Tri[curr].edges[id];
- }
- int match(ii a[]){
- int i,j,l;
- int curr=0;
- for(i=1;i<=n+n;i++){
- curr=find_next(curr,a[i]);
- if(pos[curr]==kas) return 1;
- }
- if(pos[curr]==kas) return 1;
- return 0;
- }
- //////////////////************** END *****************////////////////
- void print(int a[]){
- for(int i=1;i<=n;i++){
- printf("%d ",a[i]);
- }
- puts("");
- }
- int main(){
- int i,j,k,l,test,t=1;
- //freopen("in.txt","r",stdin);
- //freopen("out.txt","w",stdout);
- scanf("%d",&test);
- while(test--){
- //Init.......
- kas++;
- tot=0;
- root=Tri[0];
- init(&Tri[0],tot++);
- scanf("%d",&n);
- ii sum=0;
- for(j=1;j<=4;j++){
- for(i=1;i<=n;i++){
- scanf("%d",&sld[j][i]);
- sum+=sld[j][i];
- }
- }
- req=sum/(ii)n;
- printf("Case %d: ",t++);
- if(req*n!=sum){
- puts("No");
- continue;
- }
- for(i=1;i<=n;i++){
- req_arr[i]=req-sld[4][i];
- }
- for(i=1;i<=n;i++){
- for(j=1,k=i;j<=n;j++,k++){
- if(k>n) k=1;
- arr[j]=req_arr[j]-sld[3][k];
- if(arr[j]<0){
- break;
- }
- }
- //print(arr);
- if(j<=n) continue;
- add(&Tri[0],arr,i);
- }
- build();
- //puts("match");
- for(i=1;i<=n;i++){
- for(j=1,k=i;j<=n;j++,k++){
- if(k>n) k=1;
- arr[j]=sld[2][j]+sld[1][k];
- }
- for(j=1;j<=n;j++){
- arr[n+j]=arr[j];
- }
- //print(arr);
- if(match(arr)) break;
- }
- if(i<=n){
- puts("Yes");
- }
- else{
- puts("No");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement