Submission #1114279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114279		ljtunas	Nivelle (COCI20_nivelle)	C++14	110 / 110	423 ms	21316 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define all(h) h.begin(), h.end()
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 1e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

// (x, y) -> (u, v) = Ckn(u - x, x + y - u - v);
// Ckn(k, a) * Ckn(k, b) = C(a, a + b);  (k : 1 -> min(a, b))

void fixmod(int &val) {
    if (val < 0) val += MOD*MOD;
    val %= MOD;
}

int n, f[26][MAXN];
string s;
int get(int l, int r) {
	int res = 0;
	For(i, 0, 25) res += (f[i][r] - f[i][l - 1] > 0);
	return res;
}

void Progess() {
	cin >> n >> s;
	s = '$' + s;
	For(i, 1, n) {
		For (j, 0, 25)
			f[j][i] = f[j][i - 1] + (s[i] - 'a' == j);
	}
	int l = 1, r = n, cnt = get(l, r);
	For(dem, 1, 26) {
		for (int i = 1, j = 1; i <= n; ++i) {
			// if (dem == 2 && i == 7) cerr << j << '\n';
			while (j < i && get(j, i) > dem) ++j;
			if (get(j, i)*(r-l+1)<=get(l, r)*(i-j+1)) {
				cnt = get(j, i);
				l = j, r = i;
			}
			// if (dem == 2 && i == 7) cerr << j << '\n';
		}
	}
	cout << l << ' ' << r << '\n';
}

signed main(void) {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cout.tie(nullptr);

    #define task "main"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }//_______________________________
    Progess();
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

nivelle.cpp: In function 'void Progess()':
nivelle.cpp:68:20: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
   68 |  int l = 1, r = n, cnt = get(l, r);
      |                    ^~~
nivelle.cpp: In function 'int main()':
nivelle.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nivelle.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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