Submission #1017283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017283		vjudge1	Nivelle (COCI20_nivelle)	C++17	0 / 110	4 ms	1896 KiB

nivelle

#include<bits/stdc++.h>

using namespace std;

const int N = 100'010, K = 19;
int sp[N][K];

int getor(int l, int r)
{
  // cerr << l << ' ' << r << endl;
  int b = 31 - __builtin_clz(r - l);
  // cerr << b << endl;
  return sp[l][b] | sp[r - (1 << b)][b];
}

bool smaller(vector<int> a, vector<int> b)
{
  return a[0] * b[1] < b[0] * a[1];
}

int main()
{
  int n;
  string s;
  cin >> n >> s;
  int mask[n];
  for(int i = 0; i < n; i ++)
    mask[i] = 1 << (s[i] - 'a');

  for(int i = n - 1; i >= 0; i --)
    {
      sp[i][0] = mask[i];
      for(int l = 1; i + (1 << l) <= n; l++)
	sp[i][l] = sp[i][l - 1] | sp[i + 1 << (l - 1)][l - 1];
    }
  vector<int> ans;
  //   set  sz s  e 
  ans = {1, 1, 1, 1};
  for(int i = 0; i < n; i ++)
    {
      // cerr << i << endl;
      int cur = 0;
      while(cur < getor(i, n))
	{
	  int l = i, r = n + 1;
	  while(r - l > 1)
	    {
	      int m = (l + r) / 2;
	      if(getor(i, m) <= cur)
		l = m;
	      else
		r = m;
	    }
	  if(smaller({__builtin_popcount(cur), l - i, i + 1, l}, ans))
	    ans = {__builtin_popcount(cur), l - i, i + 1, l};
	  cur = getor(i, r);
	}
    }
  cout << ans[2] << ' ' << ans[3] << endl;
  return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:34:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   34 |  sp[i][l] = sp[i][l - 1] | sp[i + 1 << (l - 1)][l - 1];
      |                               ~~^~~

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