oj.uz

Submission #872681

# Submission time Handle Problem Language Result Execution time Memory
872681 2023-11-13T14:37:55 Z vjudge1 Nivelle (COCI20_nivelle) C++17
62 / 110
 1000 ms 17672 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;

const int N = 1e5 + 23;
const int LOG = 26;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n;
string s;
int a[N];
int b[N];
vector<int> vals;
pair<ldb,pii> ans = {1.0 , {1,1}};

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

void check(int x) {
	int l = 1;
	int s = __builtin_popcount(x);
	for(int i = 1 ; i<=n ; i++) {
		b[i] = (x >> a[i]) &1;
		//debug(i,b[i]);
		if(b[i] == 0) {
			if(b[i-1] == 0 || i == 1) {
				l = i+1;
				continue;
			}
			int r = i-1;
			debug((ldb)s/(r-l+1),s,(r-l+1));
			ans = min(ans, {(ldb)s/(r-l+1), {l,r}});
			l = i+1;
		}
		if(i > 1 && b[i] == b[i-1] && b[i] == 1) {
			debug(x,i,i-1);
		}
	}
	if(b[n] != 0) {
		int r = n;
		ans = min(ans, {(ldb)s/(r-l+1), {l,r}});
	}
}

bool mark[LOG+23];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>s;
	vector<int> sex;
	for(int i = 1; i<= n ; i++) {
		a[i] = s[i-1] -'a';
	}
	sex.pb(a[n]);
	vals.pb(a[n]);
	for(int i = 1; i<= n; i++) {
		if(!mark[a[i]]) {
			sex.pb(a[i]);
			int f = 0;
			for(int j = sz(sex)-1; j>= 0 ;j--) {
				int x = sex[j];
				f |= (1 << x);
				vals.pb(f);
			}
			mark[a[i]] = true;
		} else {
			sex.erase(find(all(sex),a[i]));
			sex.pb(a[i]);
			int f = 0;
			for(int j = sz(sex)-1; j>= 0 ;j--) {
				int x = sex[j];
				f |= (1 << x);
				vals.pb(f);
			}
		}
	}
	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());
	for(int x : vals) check(x);
	cout<<ans.S.F << ' '<< ans.S.S << '\n';
	return 0;
}

Compilation message

nivelle.cpp: In function 'void check(int)':
nivelle.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
nivelle.cpp:49:4: note: in expansion of macro 'debug'
   49 |    debug((ldb)s/(r-l+1),s,(r-l+1));
      |    ^~~~~
nivelle.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
nivelle.cpp:54:4: note: in expansion of macro 'debug'
   54 |    debug(x,i,i-1);
      |    ^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 860 KB Output is correct
2 Correct 109 ms 856 KB Output is correct
3 Correct 99 ms 860 KB Output is correct
4 Correct 97 ms 860 KB Output is correct
5 Correct 103 ms 856 KB Output is correct
6 Correct 161 ms 860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3092 KB Output is correct
2 Correct 7 ms 3244 KB Output is correct
3 Correct 7 ms 3092 KB Output is correct
4 Correct 8 ms 3092 KB Output is correct
5 Correct 8 ms 3092 KB Output is correct
6 Correct 9 ms 3092 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5388 KB Output is correct
2 Correct 30 ms 5904 KB Output is correct
3 Correct 31 ms 5388 KB Output is correct
4 Correct 30 ms 6868 KB Output is correct
5 Correct 35 ms 6412 KB Output is correct
6 Correct 33 ms 6668 KB Output is correct

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 17672 KB Time limit exceeded
2 Halted 0 ms 0 KB -