Facebook
From Orion, 4 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 270
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     int t,m;
  10.     int *result;//The test result array
  11.     scanf("%d",&t);//Get the test case number
  12.     result=(int*)malloc(sizeof(int)*t);//allocate memory
  13.     for (int i = 0; i < t; i++)
  14.     {  
  15.         result[i]=1;//intialise with 1
  16.         int n,*guest;
  17.         string chain;//binary string
  18.         scanf("%d",&n);// the number of hats
  19.         if(n>15){
  20.             std::cout<<"invalid";
  21.             return 0;
  22.         }
  23.         guest=(int*)malloc(sizeof(int)*n);//allocate
  24.         m+=n;
  25.         int current;//current means the first hat number
  26.         for (int j = 0; j < n; j++)
  27.         {
  28.             scanf("%d",&guest;[j]);//get the input of hat number
  29.         }
  30.         current=guest[0];
  31.         std::cin>>chain;//get the binary string
  32.         for (int j = 0; j < n; j++)
  33.         {
  34.             if (chain[j]=='1')
  35.             {  
  36.                 //check if it goes with the current guest
  37.                 if (current==(j+1))
  38.                 {
  39.                     // if it does then shift the next hat
  40.                     current=guest[j+1];
  41.                 }else{
  42.                     // if it doen't then put 0 for this test
  43.                     result[i]=0;
  44.                 }
  45.                
  46.             }else{
  47.                 if (chain[current-1]!='1')
  48.                 {
  49.                     //distribute if the current hat is not necessary for the upcoming customer, required to be happy
  50.                     current=guest[j+1];  
  51.                 }
  52.                
  53.             }
  54.            
  55.         }
  56.         free(guest);
  57.        
  58.        
  59.  
  60.     }
  61.     if(m>1000){
  62.         std::cout<<"Invalid";
  63.         return 0;
  64.     }
  65.     for (int r = 0; r < t; r++)
  66.     {  
  67.        
  68.         std::cout<<(result[r]==0?"NO":"YES");//print the test case result
  69.     }
  70.     free(result);
  71.    
  72.    
  73.     return 0;
  74. }