| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 666887 | 2022-11-29T20:42:51 Z | hyakup | Superpozicija (COCI22_superpozicija) | C++17 | 28 ms | 3900 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];
pair<int, int> q[maxn];
int main(){
int t; scanf("%d", &t );
for( int T = 0; T < t; T++){
int n; scanf("%d", &n );
char s[2*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 ){
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 | 28 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 19 ms | 384 KB | Output is correct |
| 2 | Correct | 20 ms | 1580 KB | Output is correct |
| 3 | Correct | 25 ms | 1740 KB | Output is correct |
| 4 | Correct | 21 ms | 2244 KB | Output is correct |
| 5 | Correct | 19 ms | 2316 KB | Output is correct |
| 6 | Correct | 12 ms | 2132 KB | Output is correct |
| 7 | Correct | 18 ms | 2540 KB | Output is correct |
| 8 | Correct | 18 ms | 3020 KB | Output is correct |
| 9 | Correct | 21 ms | 3384 KB | Output is correct |
| 10 | Correct | 23 ms | 3768 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 212 KB | Output is correct |
| 2 | Correct | 24 ms | 1236 KB | Output is correct |
| 3 | Correct | 24 ms | 1776 KB | Output is correct |
| 4 | Correct | 20 ms | 1900 KB | Output is correct |
| 5 | Correct | 25 ms | 2264 KB | Output is correct |
| 6 | Correct | 26 ms | 2524 KB | Output is correct |
| 7 | Correct | 12 ms | 2120 KB | Output is correct |
| 8 | Correct | 20 ms | 2736 KB | Output is correct |
| 9 | Correct | 16 ms | 3028 KB | Output is correct |
| 10 | Correct | 25 ms | 3568 KB | Output is correct |
| 11 | Correct | 28 ms | 3900 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 28 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |