제출 #1017322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017322		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	401 ms	8460 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;
	  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);
	}
      cur = getor(i, n);
      // cerr << "out : " << __builtin_popcount(cur) << ' ' << i + 1 << ' ' << n << endl;
      if(smaller({__builtin_popcount(cur), n - i, i + 1, n}, ans))
	ans = {__builtin_popcount(cur), n - i, i + 1, n};
    }
  cout << ans[2] << ' ' << ans[3] << endl;
  return 0;
}

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