제출 #922357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922357		Shayan86	Nivelle (COCI20_nivelle)	C++14	110 / 110	18 ms	788 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll A = 27;
const ll N = 1e5 + 50;
const ll Mod = 1e9 + 7;

ll n, last[N];

string s;
vector<int> vec;

bool ok(int a, int b, int c, int d){
    return (b * c <= a * d);
}

int main(){
    fast_io;

    cin >> n >> s;
    s = "$" + s;

    for(int i = 0; i < A; i++) vec.pb(0);

    int l = 0, r = 0, d = A;
    for(int i = 1; i <= n; i++){
        vec.erase(find(all(vec), last[s[i] - 'a']));
        last[s[i] - 'a'] = i;
        vec.pb(last[s[i] - 'a']); sort(all(vec));

        for(int j = 0; j < A-1; j++){
            if(!vec[j+1]) continue;
            if(ok(i - vec[j], A - j - 1, r - l + 1, d)){
                l = vec[j] + 1; r = i; d = A - j - 1;
                //cout << l << sep << r << sep << d << endl;
            }
        }
    }

    cout << l << sep << r;

}

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