oj.uz

Submission #704919

# Submission time Handle Problem Language Result Execution time Memory
704919 2023-03-03T06:44:45 Z Paul_Liao_1457 Superpozicija (COCI22_superpozicija) C++17
10 / 110
 32 ms 2016 KB 
//記得跳題
//#pragma GCC optimize("O4,unroll_loops")
//#pragma GCC target("avx2")
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
#include<random>

#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define INF (ll)(2e18)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0);

using namespace std;

string s;
int id[200005], a[200005], b[200005], suf[200005], ans[200005], who[200005];

void solve() {
  int n; cin >> n;
  cin >> s;
  int ca = 0;
  FOR (i, 0, n) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    id[a[i]] = 1; id[b[i]] = 2;
    if (s[a[i]] != s[b[i]]) ca = 1;
  }
  if (!ca) {
    int cnt = 0;
    FOR (i, 0, 2*n) {
      if (s[i] == '(') cnt++;
      else cnt --;
    }
    if (cnt) {
      cout << -1 << endl;
    } else {
      int cur = 0;
      FOR (i, 0, 2*n) {
        if (s[i] == '(' && id[i] == 1) {
          cur++;
        } else if(s[i] == ')' && id[i] == 2) {
          cur--;
          if (cur < 0) {
            cout << -1 << endl; return;
          }
        }
      }
      FOR (i, 0, n) {
        if (s[a[i]] == '(') cout << 0 << " ";
        else cout << 1 << " ";
      }
      cout << endl;
    }
  } else {
    FOR (i, 0, n) {
      who[a[i] / 2] = i;
    }
    REP (i, n-1, 0) {
      suf[i] = suf[i+1];
      if (s[2*i] == ')' || s[2*i+1] == ')') suf[i]++;
    }
    int sum = 0;
    FOR (i, 0, n) {
      if (s[2*i] == s[2*i+1]) {
        if (s[2*i] == '(') sum++;
        else sum--;
        if (sum < 0) {
          cout << -1 << endl; return;
        }
      } else {
        if (suf[i+1] >= sum + 1) {
          sum++;
          if (s[2*i] == '(') ans[who[i]] = 0;
          else ans[who[i]] = 1;
        } else {
          sum--;
          if (s[2*i] == '(') ans[who[i]] = 1;
          else ans[who[i]] = 0;
        }
      }
    }
    if (sum) {
      cout << -1 << endl;
    } else {
      FOR (i, 0, n) cout << ans[i] << " ";
      cout << endl;
    }
  }
}

signed main(){
  AC;
  int t; cin >> t;
  while (t--) {
    solve();
  }
}

/*
 vector<pair<int, int> > e[200005];
 vector<pair<int, int> > ans;

 void dfs(int now, int f,int up){
   if (up != -1) {
     ans.pb({now, up});
   }
   for (auto i:e[now]) if (i.F != f) {
     dfs(i.F, now, i.S);
   }
 }

 signed main(){
   AC;
   int n, m; cin >> n >> m;
   FOR (i, 0, m) {
     int a, b; cin >> a >> b;
     e[a].pb({b, 0});
     e[b].pb({a, 1});
   }
   dfs(1, 0, -1);
   cout << ans.size() << endl;
   for (auto i:ans) {
     cout << i.F << " " << i.S << endl;
   }
 }


 */

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 432 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 356 KB Output is correct
2 Correct 19 ms 468 KB Output is correct
3 Correct 12 ms 676 KB Output is correct
4 Correct 14 ms 852 KB Output is correct
5 Correct 13 ms 1108 KB Output is correct
6 Correct 12 ms 1232 KB Output is correct
7 Correct 10 ms 1492 KB Output is correct
8 Correct 12 ms 1664 KB Output is correct
9 Correct 13 ms 1860 KB Output is correct
10 Correct 17 ms 2016 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 70.0

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