Submission #446338

#	Time	Username	Problem	Language	Result	Execution time	Memory
446338		Dipra_Irham	Grudanje (COCI19_grudanje)	C++17	70 / 70	173 ms	14596 KiB

grudanje

#include "bits/stdc++.h"
#define pb(x) push_back(x)
#define fil(x, y) memset(x, y, sizeof(x))
#define ll long long
#define ff first
#define ss second
#define printp(x) x.ff << " " << x.ss
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp(x, y) make_pair(x,y)
#define inf 1073741823
#define infll 4611686018427387903
#define M 1000000007
#define db(x) cout << x << " ";
#define N 200007
#define sz size
#define sm 0.0000007
#define ins insert
#define ers erase
#define all(k) k.begin(), k.end()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;


int snow[N];
int cover[N];
int cnt[N][26];
int n;
string s;
pii ara[N];
int q;
bool chk(int f)
{
    fil(cover, 0);
    if(f != -1)
    {
        for(int i = 0;i <= f;i++)
        {
            cover[snow[i] - 1] = 1;
        }
    }
    for(int i = 0;i <= n;i++)
    {
        if(i == 0)
        {
            for(int j = 0;j < 26;j++)
                cnt[i][j] = 0;
        }
        else
        {
            for(int j = 0;j < 26;j++)
            {
                cnt[i][j] = cnt[i - 1][j];
            }
            if(cover[i - 1] == 0){
                cnt[i][s[i - 1] - 'a']++;
            }
        }
    }
    for(int i = 0;i < q;i++)
    {
        for(int j = 0;j < 26;j++)
        {
            if(cnt[ara[i].ss][j] - cnt[ara[i].ff - 1][j] >= 2)
                return 0;
        }
    }
    return 1;
}
int main()
{
    fastio;
    cin >> s;
    n = s.sz();
    cin >> q;
    for(int i = 0;i < q;i++)
    {
        cin >> ara[i].ff >> ara[i].ss;
    }
    for(int i = 0;i < n;i++)
    {
        cin >> snow[i];
    }
    if(chk(-1))
    {
        cout << 0 << endl;
        return 0;
    }
    int l = 0;
    int r = n - 1;
    int ans = inf;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(chk(mid))
        {
            ans = min(ans, mid);
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans + 1<< endl;
    return 0;

}

• 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