Submission #1117878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117878		vjudge1	Match (CEOI16_match)	C++17	0 / 100	1 ms	336 KiB

match

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

#define int long long
#define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")

using namespace std;
using namespace __gnu_pbds;

const int sz = 3e5+9;
const int LOG = 63;
const int MOD = 1e9+7;
const int INF = 1e18;

string s;

class seg
{
public:
    vector<int> t;
    vector<int> lazy;
    int n;
    seg(int x)
    {
        n = x;
        t.resize(n<<2, 0);
        lazy.resize(n<<2, -1);
    }
    void update(int node, int l, int r, int updateL, int updateR, int val)
    {
        if (lazy[node] != -1)
        {
            t[node] = lazy[node];
            if (l != r)
            {
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = -1;
        }
        if (l > updateR || r < updateL) return;
        if (l >= updateL && r <= updateR)
        {
            t[node] = val;
            if (l != r)
            {
                lazy[node<<2] = val;
                lazy[node<<1|1] = val;
            }
            return;
        }
        int mid = (l+r)>>1;
        update(node<<1,l,mid,updateL,updateR,val);
        update(node<<1|1,mid+1,r,updateL,updateR,val);
    }

    int query(int node, int l, int r, int idx)
    {
        if (lazy[node] != -1)
        {
            t[node] = lazy[node];
            if (l != r)
            {
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = -1;
        }
        if (l == r)
        {
            return t[node];
        }
        int mid = (l+r)>>1;
        if (idx <= mid)
        {
            return query(node<<1,l,mid,idx);
        }
        else
        {
            return query(node<<1|1,mid+1,r,idx);
        }
    }
};

bool check()
{
    if ((int)s.length() & 1)
    {
        cout << "-1\n";
        return 0;
    }
    return 1;
}

void solve()
{
    cin>>s;
    if (check())
    {
        string res = "";
        seg segt(s.length());
        for (int i = 0; i < s.length(); ++i)
        {
            int d = -1;
            for (int j = i + 1; j < s.length(); ++j)
            {
                if (s[i] == s[j] && segt.query(1, 0, s.length() - 1, j) == 0)
                {
                    d = j;
                    break;
                }
            }
            if (d != -1)
            {
                segt.update(1, 0, s.length() - 1, d, d, 1);
                res += "(";
            }
            else
            {
                res += ")";
            }
        }
        cout<<res<<'\n';
    }
}

signed main()
{
    $AzH_TxdmN$
    int t = 1;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

match.cpp: In function 'void solve()':
match.cpp:108:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int i = 0; i < s.length(); ++i)
      |                         ~~^~~~~~~~~~~~
match.cpp:111:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int j = i + 1; j < s.length(); ++j)
      |                                 ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63