(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #198914

#제출 시각아이디문제언어결과실행 시간메모리
198914dimash241Nivelle (COCI20_nivelle)C++17
110 / 110
132 ms21240 KiB
# include <bits/stdc++.h> # include <ext/pb_ds/assoc_container.hpp> # include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define _USE_MATH_DEFINES_ #define ll long long #define ld long double #define Accepted 0 #define pb push_back #define mp make_pair #define sz(x) (int)(x.size()) #define every(x) x.begin(),x.end() #define F first #define S second #define lb lower_bound #define ub upper_bound #define For(i,x,y) for (ll i = x; i <= y; i ++) #define FOr(i,x,y) for (ll i = x; i >= y; i --) #define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) // ROAD to... Red inline void Input_Output () { //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); } const double eps = 0.000001; const ld pi = acos(-1); const int maxn = 1e7 + 9; const int mod = 1e9 + 7; const ll MOD = 1e18 + 9; const ll INF = 1e18 + 123; const int inf = 2e9 + 11; const int mxn = 1e6 + 9; const int N = 6e5 + 123; const int M = 26; const int pri = 997; const int Magic = 2101; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1}; int n; int a[N]; int u[M]; int pre[N][M]; int nxt[N][M]; int f[N]; int c[N], ret; void add (int x) { u[x]++; if(u[x] == 1) ret++; } void rem (int x) { u[x] --; if (!u[x]) ret--; } int main () { SpeedForce; cin >> n; for (int i = 1; i <= n; i ++) { char ch; cin >> ch; a[i] = ch - 'a'; } for (int i = 0; i < M; i ++) { nxt[n+1][i] = n + 1; } for (int i = 1; i <= n; i ++) { for (int j = 0; j < 26; ++j) pre[i][j] = pre[i-1][j]; pre[i][a[i]] = i; } for (int i = n; i >= 1; i --) { for (int j = 0; j < 26; ++j) nxt[i][j] = nxt[i+1][j]; nxt[i][a[i]] = i; } double res = 1; pair < int, int > ans = mp(1, 1); for (int i = 1; i <= n; i ++) { vector < int > pref; for (int j = 0; j < 26; j ++) { u[j] = 0; pref.pb(pre[i][j]); } sort(pref.rbegin(), pref.rend()); ret = 0; for (int j = 0; j < pref.size(); j++) { if (!pref[j]) break; int l = 0, r = i + 1; if (j + 1 < pref.size()) l = pref[j+1]; add(a[pref[j]]); double now = ret; now /= (r - l - 1); if (now < res) { res = now; ans = mp(l + 1, r - 1); } } } cout << ans.F << ' ' << ans.S << '\n'; return Accepted; } // B...a

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

nivelle.cpp: In function 'int main()':
nivelle.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < pref.size(); j++) {
                   ~~^~~~~~~~~~~~~
nivelle.cpp:105:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j + 1 < pref.size()) l = pref[j+1];
        ~~~~~~^~~~~~~~~~~~~
#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...