Submission #591582

#	Time	Username	Problem	Language	Result	Execution time	Memory
591582		nguyen31hoang08minh2003	Nivelle (COCI20_nivelle)	C++14	110 / 110	87 ms	628 KiB

nivelle

/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|
|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ |
|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |
|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |
|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |         |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |
|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | T J 0 2 | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ |
|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\| h u 7 0 |/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ u l t 2 +----+----+----+----+----+----+----+----+----+----+
|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/| r y h 2 |\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|
|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | s       | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ |
|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  | d \|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |
|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   | a \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ y -+----+----+----+----+----+----+----+----+----+----+----+
|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |
|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |
|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ |
|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class Fraction {
private:
    ll x, y;
public:
    Fraction(const ll a, const ll b) {
        assert(a >= 0 && b > 0);
        const ll c = __gcd(a, b);
        x = a / c;
        y = b / c;
    }

    friend bool operator > (const Fraction &a, const Fraction &b) {
        return a.x * b.y > a.y * b.x;
    }

    friend bool operator < (const Fraction &a, const Fraction &b) {
        return a.x * b.y < a.y * b.x;
    }

    friend ostream& operator << (ostream &outputStream, const Fraction &f) {
        return outputStream << f.x << '/' << f.y;
    }
};

const int maxN = 100005;

int n, l, r, cnt[270];
Fraction f(1, 1);
string s;

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> n >> s;
    for (int x, y, z = 1, t; z <= 26; ++z) {
        for (x = 0, y = 0, t = 0; y < n; ++y) {
            if (!(cnt[s[y]]++))
                ++t;
            for (; t > z && x <= y; ++x)
                if (!(--cnt[s[x]]))
                    --t;
            if (t == z) {
                if (mini(f, Fraction(z, y - x + 1))) {
                    l = x;
                    r = y;
                }
            }
        }
        for (; x < n; ++x)
            --cnt[s[x]];
    }
    ++l;
    ++r;
    cout << l << ' ' << r << '\n';
    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:87:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |             if (!(cnt[s[y]]++))
      |                           ^
nivelle.cpp:90:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |                 if (!(--cnt[s[x]]))
      |                                 ^
nivelle.cpp:100:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |             --cnt[s[x]];
      |                       ^

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