제출 #637640

#제출 시각아이디문제언어결과실행 시간메모리
6376404EVERNivelle (COCI20_nivelle)C++11
24 / 110
1085 ms10856 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O2") //#pragma GCC target("avx,avx2,fma") using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define PB push_back #define ALL(i_) i_.begin(), i_.end() #define LOG2(x) (31 - __builtin_clz(x)) #define getBit(x, i) ((x >> i) & 1) #define rd(l, r) (l + rng() % (r - l + 1)) typedef long long ll; typedef long double ld; typedef pair<int, int> ii; template<class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) { x = y; return 1; } return 0; } template<class X, class Y> bool maximize(X &x, const Y &y) { X eps = 1e-9; if (x + eps < y) { x = y; return 1; } return 0; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const int mod = (int) 1e9 + 7; const int oo = (int) 1e9 + 99; const int maxn = (int) 1e5 + 11; const int LOG = (int) 17; const ii dxy[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; int n; int cnt[maxn][26]; string s; int CNT(int l, int r){ int ans = 0; for(int i = 0; i < 26; i++) ans += (cnt[r][i] - cnt[l - 1][i] > 0); return ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "NIVELLE" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n >> s; s = " " + s; for(int i = 1; i <= n; i++){ for(int j = 0; j < 26; j++){ cnt[i][j] = cnt[i - 1][j] + ((s[i] - 'a') == j); } } ld res = 1e18; pair<int, int> ans; for(int num = 1; num <= 26; num++){ for(int i = 1; i <= n - num + 1; i++){ int l = i, r = n, pos = -1; while(r - l >= 0){ int mid = (l + r) >> 1; if(CNT(i, mid) <= num){ pos = mid; l = mid + 1; } else r = mid - 1; } if(pos != -1 && CNT(i, pos) == num){ ld val = num / (1.0 * (pos - i + 1)); if(res > val){ res = val; ans = {i, pos}; } } } } cout << ans.first << " " << ans.second << "\n"; return 0; }

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

nivelle.cpp: In function 'int main()':
nivelle.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nivelle.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...