Submission #200220

# Submission time Handle Problem Language Result Execution time Memory
200220 2020-02-05T17:15:08 Z CaroLinda Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
1500 ms 90616 KB
#include <bits/stdc++.h>
     
    #define ff first
    #define ss second
     
    const int MOD = 1e8 ;
    const int MAX = 1e5+10 ;
    const int SMAX = 2e6+10 ;
    const int base = 31 ;
     
    using namespace std ;
     
    int resp[MAX] ;
     
    int get_val(char c) 
    {
        if( c == 'A' ) return 1 ;
        if( c == 'C' ) return 2 ;
        if( c == 'G' ) return 3 ;
        return 4 ;
    }
     
    struct Trie
    {
       
        struct Node
        {
            int v[5] , soma ;
            vector<int> end_here ;
            Node() { for(int i = 0 ; i < 5 ; i++ ) v[i] = soma =0 ; }
        } ;
       
        int ptr ;
        vector<Node> adj ;
        
        Trie() { adj.push_back( Node() ) ; }
        
        void add( vector<char> v, int idx, int para_somar )
        {
            
            int curr = 0 ;
            
            for(int i = 0 ; i < (int)(v.size()) ; i++ )
            {
                int val = get_val( v[i] ) ;
                adj[curr].soma += para_somar ;
                
                if( adj[curr].v[val] == 0 )
                {
                    if( para_somar == 1 ) return ;
                    adj.push_back( Node() ) ;
                    adj[curr].v[val] = ++ptr ;
                }
                
                curr = adj[curr].v[val] ;
                
            }
            
            if( para_somar == 0 )
                adj[curr].end_here.push_back(idx) ;
                
            adj[curr].soma += para_somar; 
            
            
        }
        
        void anda()
        {
            
            queue<int> fila ;
            fila.push(0) ;
            
            while(!fila.empty())
            {
                int curr = fila.front() ;
                fila.pop() ;
                    
                
                for(int i : adj[curr].end_here )
                    resp[i] = adj[curr].soma ;
                
                for(int i = 0 ; i < 5 ; i ++ )
                    if( adj[curr].v[i] > 0 )
                        fila.push( adj[curr].v[i] ) ;
                
            }
            
        }
        
        
    } ;
     
    int n , m ;
    vector<int> dif_tams ;
    bool marc_tams[SMAX] ;
    char str[MAX] ;
    vector<char> to_sell[MAX] , to_buy_pref[MAX] , to_buy_suf[MAX] ;
    vector< pair< long long int , int > > aux ;
    long long pot[SMAX] ;
    vector<long long> my_hash ;
    unordered_map<long long , int> mp ;
    Trie our_trie[MAX] ;
    string s ;
    int marc[MOD+10] ;
     
    int main()
    {
    	//Reading input
    	scanf("%d%d", &n , &m) ;
    	
    	for(int i = 1 ; i <= n ; i++ )
    	{
    	    scanf("%s", str ) ;
    	   
    	   int _n = strlen(str) ;
    	   
    	   for(int j = 0 ; j < _n ; j++ ) to_sell[i].push_back( str[j] ) ;
    	    
    	}
    	getchar() ;
    	
    	for(int i = 1 ; i <= m ; i++ )
    	{
    	    getline( cin , s ) ;
    	    int _n = s.size() , j = 0;
    	    
    	   for(; s[j] != ' ' ; j++ )
    	    to_buy_pref[i].push_back( s[j] ) ;
    	   j ++ ;
    	   
    	   for(; j < _n ; j++ ) to_buy_suf[i].push_back( s[j] ) ;
    	    
    	}
        //
        
    	
     
    	mp.reserve(m) ;
    	
    	for(int i = 1 ; i <= m ; i++ )
    	{
    	    
    	    marc_tams[ to_buy_suf[i].size() ] = true ;
    	    
    	   long long cur_sum = 0LL ;
    	    
    	  for(int j = to_buy_suf[i].size() - 1, idx = 0 ; j >= 0 ; j-- , idx++ )
    	   {
    	       cur_sum = ( cur_sum * base ) % MOD ;
    	       cur_sum = ( cur_sum + get_val( to_buy_suf[i][j] ) ) % MOD ;
    	   } 
     
    	  
    	   
    	   my_hash.push_back( cur_sum ) ;
    	   marc[cur_sum] = 1 ;
    	   
    	}
     
     
     
        int Key = 1 ;
        for(int i = 0 ; i < MOD  ; i++ ) 
            if(marc[i]) marc[i] = Key ++ ;
    	
    	
    	for(int i = 1 ; i <= m ; i++ )
        {
            my_hash[i-1] = marc[ my_hash[i-1] ] ;
            our_trie[ my_hash[i-1] ].add( to_buy_pref[i] , i , 0 ) ;
        }
        
        for(int i = 1 ; i <= SMAX ; i++ )
            if( marc_tams[i] ) dif_tams.push_back(i) ;
            
      // for(auto &p : mp ) printf("%lld %d\n" , p.ff, p.ss ) ;
        
        for(int i = 1 ; i <= n ; i++ )
        {
            
            long long cur_sum = 0LL ;
            
            for(int j = to_sell[i].size() - 1 , tot = 1 , idx = 0 ; j >= 0 ; j -- , tot++ )
            {
                cur_sum = ( cur_sum * base ) % MOD ;
                cur_sum = ( cur_sum + get_val( to_sell[i][j] ) ) % MOD ;
                
                if( tot == dif_tams[idx] ) 
                {
                    idx ++ ;
                    
                    if( marc[cur_sum] == 0 ) continue ;
                    
                    our_trie[ marc[cur_sum] ].add( to_sell[i] , -1 , 1 ) ;
                    
                }
                
            }
            
        }
        
        for(int i = 1 ; i < Key ; i++ ) our_trie[i].anda() ;
        
        for(int i = 1 ; i <= m ; i++ ) printf("%d\n" , resp[i] ) ;
    	
    }

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:109:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &n , &m) ;
      ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:113:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%s", str ) ;
          ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 158 ms 17656 KB Output is correct
2 Correct 166 ms 17784 KB Output is correct
3 Correct 162 ms 17656 KB Output is correct
4 Correct 170 ms 17788 KB Output is correct
5 Correct 159 ms 17656 KB Output is correct
6 Correct 167 ms 17660 KB Output is correct
7 Correct 166 ms 17664 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 370 ms 34104 KB Output is correct
2 Correct 374 ms 28408 KB Output is correct
3 Correct 597 ms 28536 KB Output is correct
4 Correct 609 ms 28572 KB Output is correct
5 Correct 390 ms 79608 KB Output is correct
6 Correct 371 ms 81912 KB Output is correct
7 Execution timed out 1525 ms 90616 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 213 ms 23924 KB Output is correct
2 Correct 209 ms 21368 KB Output is correct
3 Correct 207 ms 22648 KB Output is correct
4 Correct 218 ms 21612 KB Output is correct
5 Correct 200 ms 21368 KB Output is correct
6 Correct 208 ms 22644 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 158 ms 17656 KB Output is correct
2 Correct 166 ms 17784 KB Output is correct
3 Correct 162 ms 17656 KB Output is correct
4 Correct 170 ms 17788 KB Output is correct
5 Correct 159 ms 17656 KB Output is correct
6 Correct 167 ms 17660 KB Output is correct
7 Correct 166 ms 17664 KB Output is correct
8 Correct 370 ms 34104 KB Output is correct
9 Correct 374 ms 28408 KB Output is correct
10 Correct 597 ms 28536 KB Output is correct
11 Correct 609 ms 28572 KB Output is correct
12 Correct 390 ms 79608 KB Output is correct
13 Correct 371 ms 81912 KB Output is correct
14 Execution timed out 1525 ms 90616 KB Time limit exceeded
15 Halted 0 ms 0 KB -