oj.uz

Submission #666893

# Submission time Handle Problem Language Result Execution time Memory
666893 2022-11-29T21:14:50 Z hyakup Superpozicija (COCI22_superpozicija) C++17
30 / 110
 27 ms 2588 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 352 KB Output is correct
2 Correct 22 ms 580 KB Output is correct
3 Correct 16 ms 744 KB Output is correct
4 Correct 18 ms 1060 KB Output is correct
5 Correct 19 ms 1196 KB Output is correct
6 Correct 10 ms 1548 KB Output is correct
7 Correct 13 ms 1792 KB Output is correct
8 Correct 17 ms 1920 KB Output is correct
9 Correct 18 ms 2192 KB Output is correct
10 Correct 20 ms 2516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 21 ms 392 KB Output is correct
3 Correct 22 ms 596 KB Output is correct
4 Correct 22 ms 852 KB Output is correct
5 Correct 24 ms 1140 KB Output is correct
6 Correct 23 ms 1364 KB Output is correct
7 Correct 12 ms 1540 KB Output is correct
8 Correct 18 ms 1844 KB Output is correct
9 Correct 18 ms 1992 KB Output is correct
10 Correct 24 ms 2316 KB Output is correct
11 Correct 27 ms 2588 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -