Submission #1117646

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

match

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int sz=2e5+5;

const int MOD=1e9+7;

const int INF=1e18;

int arr[30];

map<char,vector<int>> mp;

void solve()
{
    string s,cur="";
    
    cin>>s;
    
    for(int i=0;i<s.size();i++)
    {
        arr[s[i]-'a']++;
        
        mp[s[i]].push_back(i);
        
        if(arr[s[i]-'a']%2==0)
            cur+=')';
        
        else
            cur+='(';
    }
    
    for(int i=0;i<cur.size();i++)
    {
        if(cur[i]==')')
            continue;
        
        int ind=-1;
        
        for(int j=i+1;j<s.size();j++)
        {
            if(s[i]==s[j])
            {
                ind=j;
                
                break;
            }
        }
        
        if(ind==-1)
        {
            cout<<-1;
            
            return;
        }
        
        int aciq=0,qapali=0;
        
        for(int j=i+1;j<ind;j++)
        {
            if(cur[j]=='(')
                aciq++;
            else
                qapali++;
        }
        
        //if(i==0)
        //    cout<<aciq<<" "<<qapali<<" "<<ind<<endl;
        
        if(aciq!=qapali)
        {
            cout<<-1;
            
            return;
        }
    }
    
    for(int i=0;i<cur.size();i++)
    {
        if(cur[i]=='(')
            continue;
        
        for(int j=0;j<mp[s[i]].size();j++)
        {
            if(mp[s[i]][j]<=i)
                continue;
            
            if(cur[mp[s[i]][j]]=='(')
            {
                cur[i]='(';
                
                cur[mp[s[i]][j]]=')';
                
                break;
            }
        }
    }
    
    cout<<cur;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
}

Compilation message (stderr)

match.cpp: In function 'void solve()':
match.cpp:23:18: 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]
   23 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
match.cpp:36:18: 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]
   36 |     for(int i=0;i<cur.size();i++)
      |                 ~^~~~~~~~~~~
match.cpp:43:24: 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]
   43 |         for(int j=i+1;j<s.size();j++)
      |                       ~^~~~~~~~~
match.cpp:81:18: 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]
   81 |     for(int i=0;i<cur.size();i++)
      |                 ~^~~~~~~~~~~
match.cpp:86:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int j=0;j<mp[s[i]].size();j++)
      |                     ~^~~~~~~~~~~~~~~~

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