Submission #704963

#	Time	Username	Problem	Language	Result	Execution time	Memory
704963		Paul_Liao_1457	Superpozicija (COCI22_superpozicija)	C++17	10 / 110	190 ms	2012 KiB

Main

//記得跳題
//#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(n & 1) {
    cout << -1 << endl; return;
  }
  
  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 if(n <= 11) {
    FOR (m, 0, 1<<n) {
      string tmp = s;
      FOR (i, 0, n) {
        if (m & (1<<i)) {
          tmp[a[i]] = s[a[i]];
          tmp[b[i]] = '?';
        } else {
          tmp[a[i]] = '?';
          tmp[b[i]] = s[b[i]];
        }
      }
      // cout << "tmp = " << tmp << endl;
      bool ok = 1;
      int sum = 0;
      FOR (i, 0, 2*n) {
        if (tmp[i] != '?') {
          if (tmp[i] == '(') sum++;
          else sum--;
          if (sum < 0){
            ok = 0;
            break;
          }
        }
      }
      if (ok && !sum) {
        FOR (i, 0, n) {
          if (m & (1<<i)) {
            if (i != n-1) cout << 0 << " ";
            else cout << 0 << endl;
          } else {
            if (i != n-1) cout << 1 << " ";
            else cout << 1 << endl;
          }
        }
        //cout << endl;
        return;
      }
    }
    cout << -1 << endl;
  } else {
    FOR (i, 0, n) {
      ans[i] = 0;
      who[a[i] / 2] = i;
    }
    suf[n] = 0;
    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 < 0) {
            cout << -1 << endl; return;
          }
        }
      }
    }
    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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70