Submission #443915

#	Time	Username	Problem	Language	Result	Execution time	Memory
443915		MahfuzAhmed	Grudanje (COCI19_grudanje)	C++14	0 / 70	49 ms	3532 KiB

grudanje

/**
 *  author: mahfuzz
 *  created: 12.07.2021
**/
 
#include <bits/stdc++.h>
using namespace std;
#define trace(x) cerr << '>' << #x << ':' << x << endl;
#define all(p) p.begin(),p.end()
typedef long long ll;

#define pii pair<int, int>
 
int main(int argc, char* argv[]){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
	
	string s; cin >> s;
    int n = s.size();
    
    int q; cin >> q;
    vector<pii> vec;
    
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        vec.push_back({l, r});
    }
    
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    auto check = [&](int x){
        string temp = s;
    
        for(int k = 0; k < x; k++){
            temp[arr[k] - 1] = '*';
        }
            
        int g[26][26] = {{0}};
        
        for(int i = 0; i < 26; i++){
            char c = 'a' + i;
            
            for(int j = 0; temp[j]; j++){
                if(temp[j] == c){
                    g[i][j] = g[i][(j == 0 ? 0 : j - 1)] + 1;
                }else{
                    g[i][j] = g[i][(j == 0 ? 0 : j - 1)];
                }
            }
        }
        
        for(auto a : vec){
            int l = a.first, r = a.second;
            for(int i = 0; i < 26; i++){
                if(l - 2 < 0 && g[i][r - 1] > 1)
                    return false;
                else if(g[i][r - 1] - g[i][l - 2] > 1)
                    return false;
            }
        }
        
        return true;
    };
    
    if(check(0)){
        cout << "0\n";
        return 0;
    }
    int l = 1, r = n;
    int ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

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