Submission #1196182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196182		Mousa_Aboubaker	Sequence (APIO23_sequence)	C++20	0 / 100	149 ms	33608 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <typename T>
using o_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

int sequence(int N, vector<int> A) {
  // subtask 4
  // binary search for the answer for the case of 1 and 3
  // the case of 2, sort all the array, and remove elements greedily until you get 2 as the median
  // this is if there was 3 distinct numbers
  // in case of only 2 distinct, return the maximum of them
  // in case of only 1 distinct number, return N
  map<int, int> mp;
  for(int i = 0; i < N; i++)
    mp[A[i]]++;
  if(mp.size() == 1)
  {
    return mp.begin()->second;
  }
  if(mp.size() == 2)
  {
    return max(mp.begin()->second, mp.rbegin()->second);
  }
  // we got 1, 2, 3 in our sequence
  vector idx(4, deque<int>());
  for(int i = 0; i < N; i++)
    idx[A[i]].push_back(i);
  vector pref(N + 1, vector<int>(4));
  for(int i = 0; i < N; i++)
  {
    if(i)
      pref[i] = pref[i - 1];
    pref[i][A[i]]++;
  }
  int mx = 1;
  int l = 1, r = mp[1], ans = 1;
  while(l <= r)
  {
    int md = (l + r) / 2;
    bool can = false;
    for(int i = md - 1; i < idx[1].size(); i++)
    {
      int j = idx[1][i];
      int k = idx[1][i - md + 1];
      int p = pref[j][1] - (k ? pref[k - 1][1] : 0);
      int others = j - k + 1 - p;
      int all = p + others;
      can |= p >= (all + 1) / 2;
    }
    if(can)
    {
      l = md + 1;
      ans = md;
    }
    else
    {
      r = md - 1;
    }
  }
  mx = max(mx, ans);
  l = 1, r = mp[3], ans = 1;
  while(l <= r)
  {
    int md = (l + r) / 2;
    bool can = false;
    for(int i = md - 1; i < idx[3].size(); i++)
    {
      int j = idx[3][i];
      int k = idx[3][i - md + 1];
      int p = pref[j][3] - (k ? pref[k - 1][3] : 0);
      int others = j - k + 1 - p;
      int all = p + others;
      can |= p >= (all + 1) / 2;
    }
    if(can)
    {
      l = md + 1;
      ans = md;
    }
    else
    {
      r = md - 1;
    }
  }
  mx = max(mx, ans);
  l = 1, r = mp[2], ans = 1;
  while(l <= r)
  {
    int md = (l + r) / 2;
    bool can = false;
    for(int i = md - 1; i < idx[2].size(); i++)
    {
      int j = idx[2][i];
      int k = idx[2][i - md + 1];
      int p = pref[j][2] - (k ? pref[k - 1][2] : 0);
      int others = j - k + 1 - p;
      int all = p + others;
      can |= p >= (all + 1) / 2;
    }
    if(can)
    {
      l = md + 1;
      ans = md;
    }
    else
    {
      r = md - 1;
    }
  }
  mx = max(mx, ans);
  // the answer for 2 needs more, but let's submit this
  return mx;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18