| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 666893 | 2022-11-29T21:14:50 Z | hyakup | Superpozicija (COCI22_superpozicija) | C++17 | 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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 26 ms | 340 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 26 ms | 340 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |