Submission #666893

#	Time	Username	Problem	Language	Result	Execution time	Memory
666893		hyakup	Superpozicija (COCI22_superpozicija)	C++17	30 / 110	27 ms	2588 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

bool ja_usou[maxn], retirado[2*maxn];

int id_query[2*maxn];
int resp[maxn];

char s[2*maxn];

pair<int, int> q[maxn];

int main(){
    
    int t; scanf("%d", &t );
    
    for( int T = 0; T < t; T++){
        
        int n; scanf("%d", &n );
        
        scanf(" %s", s );
        
        int abertos = 0, fechados = 0;
        
        for( int i = 1; i <= n; i++ ){
            
            int a, b; scanf("%d %d", &a, &b );
            
            a--, b--;
            
            q[i] = { a, b };
            
            if( s[a] == s[b] ){
                
                //printf("iguais\n");
                
                if( s[a] == '(' ){
                    
                    resp[i] = 0;
                    retirado[b] = true;
                    
                    abertos++;
                    
                } 
                else{
                    
                    resp[i] = 1;
                    retirado[a] = true;
                    
                    fechados++;
                    
                } 
                
                ja_usou[i] = true;
            }
            
            id_query[a] = i;
            id_query[b] = i;
        }
        
        if( n%2 == 1 || abertos > n/2 || fechados > n/2 ){
            
            printf("-1\n");
            
            for( int i = 0; i < n; i++ ){
            
                ja_usou[i + 1] = false;
                retirado[2*i] = retirado[2*i + 1] = false;
            }
            
            continue;
        }
        
        int tam = strlen(s);
        
        //printf("ok1\n");
        
        for( int i = 0; i < tam; i++ ){
            
            if( abertos == n/2 ) break;
            
            if( ja_usou[ id_query[i] ] ) continue;
            
            
            if( s[i] == '(' ){
                
                // printf("%d ", i );
                
                abertos++;
                
                ja_usou[ id_query[i] ] = true;
                
                if( i == q[ id_query[i] ].first ){
                    
                    resp[ id_query[i] ] = 0;
                    retirado[ q[ id_query[i] ].second ] = true;
                } 
                else{
                    
                   resp[ id_query[i] ] = 1; 
                   retirado[ q[ id_query[i] ].first ] = true;
                } 
            }
        }
        
        //printf("\nok2\n");
        
        for( int i = tam - 1; i >= 0; i-- ){
            
            //printf("id %d bool %d\n", id_query[i], ja_usou[ id_query[i] ]);
            
            if( fechados == n/2 ) break;
            
            if( ja_usou[ id_query[i] ] ) continue;
            
            if( s[i] == ')' ){
                
                //printf("%d ", i );
                
                fechados++;
                
                ja_usou[ id_query[i] ] = true;
                
                if( i == q[ id_query[i] ].first ){
                    
                    resp[ id_query[i] ] = 0;
                    retirado[ q[ id_query[i] ].second ] = true;
                } 
                else{
                    
                   resp[ id_query[i] ] = 1; 
                   retirado[ q[ id_query[i] ].first ] = true;
                } 
            }
        }
        
        int cont = 0;
        bool deu_bom = true;
        
        //printf("\nok3\n");
        
        for( int i = 0; i < tam; i++ ){
            
            if( !retirado[i] ){
                
                //printf("%d %c\n", i, s[i] );
                
                if( s[i] == '(' ) cont++;
                else cont--;
                
                if( cont < 0 ){
                    
                    deu_bom = false;
                    
                    break;
                }
            }
        }
        
        if( cont > 0 ) deu_bom = false;
        
        if( !deu_bom ){
            
            printf("-1\n");
            
            for( int i = 0; i < n; i++ ){
            
                ja_usou[i + 1] = false;
                retirado[2*i] = retirado[2*i + 1] = false;
            }
            
            continue;
        }
        
        for( int i = 1; i <= n; i++ ) printf("%d ", resp[i] );
        
        if( T != t - 1 ) printf("\n");
        
        for( int i = 0; i < n; i++ ){
            
            ja_usou[i + 1] = false;
            retirado[2*i] = retirado[2*i + 1] = false;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:17:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     int t; scanf("%d", &t );
      |            ~~~~~^~~~~~~~~~~
Main.cpp:21:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         int n; scanf("%d", &n );
      |                ~~~~~^~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %s", s );
      |         ~~~~~^~~~~~~~~~~
Main.cpp:29:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |             int a, b; scanf("%d %d", &a, &b );
      |                       ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 70