제출 #580978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580978		AGE	Nivelle (COCI20_nivelle)	C++14	62 / 110	386 ms	5208 KiB

nivelle

#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back
 
using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
char x[6]={'a','b','c','d','e'};
vector<int>v;
int vis[10];
double anss=1e18;
int LL,RR;
int freq[N][6],n;
bool ok(int mid,int l){
 
    if(l+mid-1>=n)
        return 0;
 
    for(int i=0;i<5;i++){
 
        int x;
        if(l==0)
            x=freq[l+mid-1][i];
 
        else
            x=freq[l+mid-1][i]-freq[l-1][i];
 
        if(vis[i]==0&&x!=0)
            return 0;
 
    }
 
    return 1;
 
}
void bt(int index){
 
    if(index==5){
 
        for(int i=0;i<n;i++){
 
            int l=0,r=n;
            while(l<r){
 
                int mid=(l+r+1)/2;
                if(ok(mid,i))
                    l=mid;
 
                else r=mid-1;
 
            }
 
            double num=0;
            for(int i=0;i<5;i++)
                if(vis[i])
                    num++;
 
            double len=l;
 
            if(num/l<anss)
                anss=num/l,LL=i,RR=i+l-1;
 
        }
 
        return ;
 
    }
 
    vis[x[index]-'a']=1;
    bt(index+1);
    vis[x[index]-'a']=0;
    bt(index+1);
 
}
 
main()
{
    cin>>n;
    set<int>st;
 
    string s;
    cin>>s;
    if(n<=2000){
 
        double ans=1e18;
        int L,R;
        for(int i=0;i<n;i++){
            st.clear();
            for(int j=i;j<n;j++){
 
                st.insert(s[j]);
                double num=st.size();
                double len=(double)j-i+1;
 
                if(num/len<ans){
 
                    ans=num/len;
                    L=i,R=j;
 
                }
 
            }
        }
        cout<<L+1<<" "<<R+1<<endl;
 
    }
 
    else{
 
        for(int j=0;j<5;j++)
            freq[0][j]=(j==(s[0]-'a'));
 
        for(int i=1;i<n;i++)
            for(int j=0;j<5;j++)
                freq[i][j]=freq[i-1][j]+(j==(s[i]-'a'));
 
        bt(0);
        
        cout<<LL+1<<" "<<RR+1<<endl;
    }
 
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

nivelle.cpp: In function 'void bt(long long int)':
nivelle.cpp:59:20: warning: unused variable 'len' [-Wunused-variable]
   59 |             double len=l;
      |                    ^~~
nivelle.cpp: At global scope:
nivelle.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
nivelle.cpp: In function 'int main()':
nivelle.cpp:105:27: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         cout<<L+1<<" "<<R+1<<endl;
      |                           ^
nivelle.cpp:105:17: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         cout<<L+1<<" "<<R+1<<endl;
      |                 ^

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 0 / 48