Submission #443428

#	Time	Username	Problem	Language	Result	Execution time	Memory
443428		colossal_pepe	Grudanje (COCI19_grudanje)	C++17	70 / 70	480 ms	13776 KiB

grudanje

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

string s;
int q, snowballs[100005];
vector<pair<int, int>> subwords;

bool check(int g) {
    int pref[26][s.size()];
    memset(pref, 0, sizeof(pref));
    for (int i = 0; i < s.size(); i++) {
        pref[s[i] - 'a'][i] = 1;
    }
    for (int i = 0; i < g; i++) {
        pref[s[snowballs[i]] - 'a'][snowballs[i]] = 0;
    }
    for (int i = 0; i < 26; i++) {
        for (int j = 1; j < s.size(); j++) {
            pref[i][j] += pref[i][j - 1];
        }
    }
    for (pair<int, int> sw: subwords) {
        for (int i = 0; i < 26; i++) {
            if (sw.first > 0) {
                if (pref[i][sw.second] - pref[i][sw.first - 1] > 1) return 0;
            } else {
                if (pref[i][sw.second] > 1) return 0;
            }
        }
    }
    return 1;
}

int solve() {
    int l = 0, r = s.size();
    while (r - l > 5) {
        int mid = (l + r)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    for (int i = l; i <= r; i++) {
        if (check(i)) return i;
    }
    return r;
}

int main() {
    cin >> s >> q;
    subwords.resize(q);
    for (int i = 0; i < q; i++) {
        cin >> subwords[i].first >> subwords[i].second;
        subwords[i].first--, subwords[i].second--;
    }
    for (int i = 0; i < s.size(); i++) {
        cin >> snowballs[i];
        snowballs[i]--;
    }
    cout << solve() << endl;
    return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'bool check(int)':
grudanje.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
grudanje.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int j = 1; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
grudanje.cpp: In function 'int main()':
grudanje.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7