oj.uz

Submission #236997

# Submission time Handle Problem Language Result Execution time Memory
236997 2020-06-04T07:56:29 Z Sorting Match (CEOI16_match) C++14
100 / 100
 77 ms 17784 KB 
#include <bits/stdc++.h>

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::__cxx11::string&, int, std::array<long long int, 2>)':
match.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(curr.size() > (n - pos))
        ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 7 ms 1408 KB Output is correct
9 Correct 7 ms 1536 KB Output is correct
10 Correct 8 ms 1664 KB Output is correct
11 Correct 8 ms 1664 KB Output is correct
12 Correct 48 ms 11256 KB Output is correct
13 Correct 50 ms 12152 KB Output is correct
14 Correct 52 ms 13048 KB Output is correct
15 Correct 23 ms 11264 KB Output is correct
16 Correct 23 ms 11264 KB Output is correct
17 Correct 48 ms 13816 KB Output is correct
18 Correct 26 ms 12544 KB Output is correct
19 Correct 77 ms 17256 KB Output is correct
20 Correct 41 ms 11256 KB Output is correct
21 Correct 68 ms 17784 KB Output is correct