Submission #340510

#	Time	Username	Problem	Language	Result	Execution time	Memory
340510		A_D	Grudanje (COCI19_grudanje)	C++14	70 / 70	499 ms	18480 KiB

grudanje

/*
ID: antwand1
TASK: barn1
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define du long double
#define F first
#define S second
using namespace std;
const int N=1e5+1;
string s;
int n,q;
int pre[N][26];
int l[N];
int r[N];
int p[N];
set<int> st;
bool ok(int mid)
{
    st.clear();
    for(int i=1;i<=mid;i++)st.insert(p[i]);
    for(int i=1;i<=n;i++){
        bool o=1;
        if(st.find(i)!=st.end())o=0;
        for(int j=0;j<26;j++){
            pre[i][j]=pre[i-1][j]+(s[i]-'a'==j&&o);
        }
    }
    for(int i=1;i<=q;i++){
        for(int j=0;j<26;j++){
            if(pre[r[i]][j]-pre[l[i]-1][j]>1){
                return 0;
            }
        }
    }
    return 1;
}

main()
{
    //freopen("barn1.in","r",stdin);freopen("barn1.out","w",stdout);
    cin>>s;
    n=s.size();
    s="#"+s;
    cin>>q;
    for(int i=1;i<=q;i++){
        scanf("%d",&l[i]);
        scanf("%d",&r[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    int low=0,hig=n,ans;
    while(low<=hig){
        int mid=(low+hig)/2;
        if(ok(mid)){
            ans=mid;
            hig=mid-1;
        }
        else low=mid+1;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

grudanje.cpp:41:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main()
      |      ^
grudanje.cpp: In function 'int main()':
grudanje.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         scanf("%d",&l[i]);
      |         ~~~~~^~~~~~~~~~~~
grudanje.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |         scanf("%d",&r[i]);
      |         ~~~~~^~~~~~~~~~~~
grudanje.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d",&p[i]);
      |         ~~~~~^~~~~~~~~~~~
grudanje.cpp:64:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     cout<<ans<<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