Submission #228488

#	Time	Username	Problem	Language	Result	Execution time	Memory
228488		Ruxandra985	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	38 ms	6380 KiB

ho_t2

#include <bits/stdc++.h>
#define DIMN 200010
using namespace std;
char s[DIMN];
int fi[DIMN] , fj[DIMN] , fo[DIMN];
vector <pair <int,int> > vi , vj;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , k , i , st , dr , mid , j , sol;
    fscanf (fin,"%d%d\n",&n,&k);
    fgets (s + 1 , n + 10 , fin);

    for (i = 1 ; i <= n ; i++){
        fj[i] = fj[i - 1];
        fo[i] = fo[i - 1];
        fi[i] = fi[i - 1];
        if (s[i] == 'J')
            fj[i]++;
        else if (s[i] == 'O')
            fo[i]++;
        else fi[i]++;
    }

    sol = n;

    for (i = 1 ; i <= n ; i++){

        st = i;
        dr = n;
        while (st <= dr){

            mid = (st + dr)/2;
            if (fj[mid] - fj[i - 1] >= k)
                dr = mid - 1;
            else st = mid + 1;

        }
        if (st <= n)
            vj.push_back(make_pair(st , st - i + 1 - k));

        /// --------------------------------------------------------------------

        /// --------------------------------------------------------------------

        st = i;
        dr = n;
        while (st <= dr){

            mid = (st + dr)/2;
            if (fi[mid] - fi[i - 1] >= k)
                dr = mid - 1;
            else st = mid + 1;

        }
        if (st <= n)
            vi.push_back(make_pair( i , st - i + 1 - k ));


    }
    /// vj si vi sunt in ordine crescatoare

    j = 0;

    for (i = 0 ; i < vj.size() ; i++){

        while (j < vi.size() && fo[vi[j].first - 1] - fo[vj[i].first] < k)
            j++;

        if (j == vi.size())
            break;

        //printf ("%d %d\n" , vi[j].first - 1 , vj[i].first + 1);

        sol = min(sol , vi[j].second + vj[i].second + vi[j].first - 1 - vj[i].first - k);

    }


    if (sol == n)
        sol = -1;
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < vj.size() ; i++){
                  ~~^~~~~~~~~~~
ho_t2.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < vi.size() && fo[vi[j].first - 1] - fo[vj[i].first] < k)
                ~~^~~~~~~~~~~
ho_t2.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j == vi.size())
             ~~^~~~~~~~~~~~
ho_t2.cpp:12:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d\n",&n,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:13:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets (s + 1 , n + 10 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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