Submission #230632

#	Time	Username	Problem	Language	Result	Execution time	Memory
230632		AlexLuchianov	JJOOII 2 (JOI20_ho_t2)	C++14	1 / 100	2080 ms	384 KiB

ho_t2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <set>

using namespace std;

using ll = long long;

int const nmax = 200000;

char s[5 + nmax];
vector<int> sets[3];

int lowerthan(vector<int> &v, int target){
  int x = 0;
  for(int jump = (1 << 20); 0 < jump; jump--)
    if(x + jump < v.size() && v[x + jump] <= target)
      x += jump;
  return x;
}

int eval(int n, int k, int stop){
  int init = stop;

  for(int h = 2; 0 <= h; h--){
    int pos = lowerthan(sets[h], stop);
    if(pos < k)
      return nmax * 2;
    stop = sets[h][pos - k + 1] - 1;
  }
  return n - 3 * k - (n - init) - stop;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  sets[0].push_back(0);
  sets[1].push_back(0);
  sets[2].push_back(0);

  for(int i = 1; i <= n; i++) {
    char ch;
    cin >> ch;
    if(ch == 'J')
      sets[0].push_back(i);
    else if(ch == 'O')
      sets[1].push_back(i);
    else
      sets[2].push_back(i);
  }

  int result = nmax * 2;
  for(int i = 1; i < sets[2].size(); i++)
    result = min(result, eval(n, k, sets[2][i]));

  if(result < nmax * 2)
    cout << result;
  else
    cout << -1;
  return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int lowerthan(std::vector<int>&, int)':
ho_t2.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(x + jump < v.size() && v[x + jump] <= target)
        ~~~~~~~~~^~~~~~~~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < sets[2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87