oj.uz

Submission #309613

# Submission time Handle Problem Language Result Execution time Memory
309613 2020-10-04T00:17:50 Z ant101 Match (CEOI16_match) C++14
100 / 100
 69 ms 19320 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include <array>
using namespace std;

#define ll long long

const ll k_Mods[2]{(ll)(1e9 + 7), (ll)(1e9 + 103)};
const ll k_Bases[2]{29, 43};

const int k_N = 1e5 + 7;

string s;
int n;

ll powers[2][k_N];

map<array<ll, 2>, vector<int>> c;
array<ll, 2> hash_arr[k_N];

bool check(string &curr, int pos, array<ll, 2> curr_hash){
    c[curr_hash].push_back(pos);
    hash_arr[pos] = curr_hash;
    
    if(curr == "" && pos == n)
        return true;
    if(curr.size() > (n - pos))
        return false;
    
    if(curr != "" && curr.back() == s[pos]){
        curr.pop_back();
        
        for(int i = 0; i <= 1; ++i){
            curr_hash[i] -= powers[i][curr.size()] * (s[pos] - 'a' + 1);
            curr_hash[i] %= k_Mods[i];
            if(curr_hash[i] < 0)
                curr_hash[i] += k_Mods[i];
        }
        
        bool answer = check(curr, pos + 1, curr_hash);
        curr += s[pos];
        
        return answer;
    }
    
    curr += s[pos];
    
    for(int i = 0; i <= 1; ++i){
        curr_hash[i] += powers[i][curr.size() - 1] * (s[pos] - 'a' + 1);
        curr_hash[i] %= k_Mods[i];
    }
    
    bool answer = check(curr, pos + 1, curr_hash);
    curr.pop_back();
    
    return answer;
}

char answer[k_N];
void solve(int l, int r){
    if(l > r)
        return;
    
    answer[l] = '(';
    
    vector<int> &v = c[hash_arr[l + 1]];
    int x = *(upper_bound(v.begin(), v.end(), r + 1) - 1);
    
    answer[x] = ')';
    
    solve(l + 1, x - 1);
    solve(x + 1, r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> s;
    n = s.size();
    
    powers[0][0] = 1;
    powers[1][0] = 1;
    
    for(int i = 0; i <= 1; ++i)
        for(int j = 1; j <= n; ++j)
            powers[i][j] = (powers[i][j - 1] * k_Bases[i]) % k_Mods[i];
    
    string curr = "";
    if(!check(curr, 0, {0, 0})){
        cout << "-1\n";
        return 0;
    }
    
    solve(0, n - 1);
    
    for(int i = 0; i < n; ++i)
        cout << answer[i];
    cout << "\n";
}

Compilation message

match.cpp: In function 'bool check(std::string&, int, std::array<long long int, 2>)':
match.cpp:42:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     if(curr.size() > (n - pos))
      |        ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 4 ms 1536 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 4 ms 1792 KB Output is correct
11 Correct 4 ms 1792 KB Output is correct
12 Correct 41 ms 12152 KB Output is correct
13 Correct 45 ms 13176 KB Output is correct
14 Correct 50 ms 14072 KB Output is correct
15 Correct 23 ms 12416 KB Output is correct
16 Correct 22 ms 12416 KB Output is correct
17 Correct 45 ms 15096 KB Output is correct
18 Correct 25 ms 13952 KB Output is correct
19 Correct 66 ms 18680 KB Output is correct
20 Correct 39 ms 12160 KB Output is correct
21 Correct 69 ms 19320 KB Output is correct