Submission #306359

#	Time	Username	Problem	Language	Result	Execution time	Memory
306359		dolijan	Grudanje (COCI19_grudanje)	C++14	70 / 70	380 ms	14236 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
vector<int> brisi;
vector<pair<int,int> > sub;
bool ok(int x,string s)
{
    for(int i=0;i<=x;i++) s[brisi[i]-1]='*';
    int n=s.length();
    int pref[n][26];
    for(int i=0;i<26;i++)
    {
        if(s[0]-'a'==i) pref[0][i]=1;
        else pref[0][i]=0;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<26;j++)
        {
            if(s[i]-'a'==j) pref[i][j]=pref[i-1][j]+1;
            else pref[i][j]=pref[i-1][j];
        }
    }
    bool li=true;
    int q=sub.size();
    for(int i=0;i<q;i++)
    {
        int l=sub[i].first,r=sub[i].second;
        if(l==0)
        {
            for(int j=0;j<26;j++)
            {
                if(pref[r][j]>1) li=false;
            }
        }
        else
        {
            for(int j=0;j<26;j++)
            {
                if(pref[r][j]-pref[l-1][j]>1) li=false;
            }
        }
    }
    return li;
}
int main()
{
    string s;
    cin>>s;
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int l,r;
        cin>>l>>r;
        l--; r--;
        sub.push_back(make_pair(l,r));
    }
    int n=s.length();
    for(int i=0;i<n;i++)
    {
        int in;
        cin>>in;
        brisi.push_back(in);
    }
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(ok(mid,s))
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    if(ok(-1,s)) cout<<0<<endl;
    else cout<<l+1<<endl;
}

• 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