OJ Board

Code: Select all

*** DELETED ***

Code: Select all

6

{}
0 

{{},{},{}}
1 0

{{},{1,2,3},{}}
1 1

{7,6,5,4,3,2,1}
4

{{{{{1}}}}}
0 0 0 0 0

{{{{{{{{1,2,3}}},{{{}}},{{{4},{5}},{{6}}}}}}}}
0 0 0 0 2 0 1 0

Code: Select all

Case 1:
Invalid query!

Case 2:
Invalid query!

Case 3:
2

Case 4:
3

Case 5:
1

Case 6:
5

Code: Select all

#include <stdio.h>
#include <ctype.h>

/* declarations */

char array[13000000];
void read_array(void);
int skip_element(int *parsepos);
int get_element(int level, int *parsepos);
/* array[] contains the first line of the input with spaces removed
   it's declared 13 mln because we can have 1 mln numbers of max 10 digits with braces and commas
   
   read_array() reads it from the input
   
   skip_element() advances parsepos over the current element, which is either a number or a pair
   of matching braces '{' and '}'
   
   get_element() recusively accesses the elements indexed by the query, calling skip_element() to
   get to the indexed element. at the bottom level it finds the number and leaves parsepos
   pointing to it
   
   get_element() and skip_element() use and update the referenced variable parsepos that indexes
   into array[]; they return negative numbers in case of error conditions
   */

int subscript[128];
int subscripts;
void read_query(void);
/* subscript[] contains the indexes from the second line of the input
   read_query() reads them from the input
   */

int read_number(void);
void skip_line(void);
/* helper functions:
   read_number() reads a number from the input and advances to the next line
   skip_line() advances to the next line in the input
   */

int main(void);
/* main() reads the number of cases and processes them one by one
   reads the input, calls get_element() to process it and prints the result
   */


/* definitions */

int main(void){
   int cases,caseno;
   int parsepos;
   
   cases=read_number();
   for(caseno=1;caseno<=cases;caseno++){
      if(caseno>1) printf("\n");
      printf("Case %d:\n",caseno);
      skip_line();
      read_array();
      read_query();
      parsepos=0;
      if(get_element(0,&parsepos)<0) printf("Invalid query!\n");
      else{
         while(isdigit(array[parsepos])) putchar(array[parsepos++]);
         putchar('\n');
         }
      }
   return 0;
   }
   
void skip_line(void){

   while(getchar()!='\n');
   }
   
int read_number(void){
   int result=0;
   int c;
   
   while(!isdigit(c=getchar()));
   while(isdigit(c)){
      result=10*result+c-'0';
      c=getchar();
      }
   while(c!='\n') c=getchar();
   return result;
   }
   
void read_query(void){
   int c;
   int sign;
   
   subscripts=0;
   c=getchar();
   while((c!='\n')&&(c!=EOF)){
      subscript[subscripts]=0;
      sign=1;
      while(!isdigit(c)&&(c!='\n')&&(c!=EOF)){
         if(c=='-') sign*=-1;
         c=getchar();
         }
      if((c=='\n')||(c==EOF)) break;
      while(isdigit(c)){
         subscript[subscripts]=10*subscript[subscripts]+c-'0';
         c=getchar();
         }
      subscript[subscripts++]*=sign;
      }
   }
   
void read_array(void){
   char *ptr=array;
   
   while((*ptr=getchar())!='\n'){
      if(!isspace(*ptr)) ptr++;
      }
   *ptr='\0';
   }

int skip_element(int *parsepos){
   int nesting=0;
   
   if(isdigit(array[*parsepos])){
      while(isdigit(++(*parsepos)));
      }
   else{
      if(array[*parsepos]!='{') return -1;
      do{
         switch(array[(*parsepos)++]){
         case '{':
            nesting++;
            break;
         case '}':
            nesting--;
            break;
         case '\0':
            return -2;
            }
         }while(nesting);
      }
   return 0;
   }

int get_element(int level, int *parsepos){
   int i;
   int result;

   if(level==subscripts){
      if(!isdigit(array[*parsepos])) return -3;
      else return 0;
      }
   else{
      if(array[(*parsepos)++]!='{') return -4;
      if(subscript[level]<0) return -6;
      for(i=0;i<subscript[level];i++){
         if(result=skip_element(parsepos)) return result;
         if(array[(*parsepos)++]!=',') return -5;
         }
      return get_element(level+1,parsepos);
      }
   }