Submission #443880

#	Time	Username	Problem	Language	Result	Execution time	Memory
443880		MahfuzAhmed	Grudanje (COCI19_grudanje)	C++14	35 / 70	2082 ms	3620 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] = '*';
        }
        
        for(auto a : vec){
            int l = a.first, r = a.second;
            
            int mark[27] = {0};
            for(int k = l - 1; k < r; k++){
                if(temp[k] == '*') continue;
                
                if(mark[temp[k] - 'a'])
                    return false;
                else
                    mark[temp[k] - 'a'] = true;
            }
        }
        
        
        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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7