Submission #639847

#	Time	Username	Problem	Language	Result	Execution time	Memory
639847		danikoynov	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	17 ms	10740 KiB

ho_t2

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;
int n, k, a[maxn], nxt[maxn][3], cur[maxn];
string s;
vector < int > path[3];
void solve()
{
    cin >> n >> k >> s;
    for (int i = 0; i < n; i ++)
    {
        if (s[i] == 'J')
            a[i + 1] = 0;
        else
        if (s[i] == 'O')
            a[i + 1] = 1;
        else
            a[i + 1] = 2;
    }

    int last0, last1, last2;
    last0 = last1 = last2 = n + 1;
    for (int i = n; i > 0; i --)
    {
        nxt[i][0] = last0;
        nxt[i][1] = last1;
        nxt[i][2] = last2;

        if (a[i] == 0)
            last0 = i;
        if (a[i] == 1)
            last1 = i;
        if (a[i] == 2)
            last2 = i;
    }



    for (int i = 1; i <= n; i ++)
    {
        cur[i] = path[a[i]].size();
        path[a[i]].push_back(i);
    }

    while(path[0].size() < 2 * n)
        path[0].push_back(n + 1);
    while(path[1].size() < 2 * n)
        path[1].push_back(n + 1);
    while(path[2].size() < 2 * n)
        path[2].push_back(n + 1);

        int ans = 1e9;
    for (int i = 1; i <= n; i ++)
    {
        int pos = i;
        if (a[pos] != 0)
            pos = nxt[pos][0];
            if (pos == n + 1)
                break;
        pos = path[a[pos]][cur[pos] + k - 1];
        if (pos == n + 1)
            break;
        pos = nxt[pos][1];
        if (pos == n + 1)
            break;
        pos = path[a[pos]][cur[pos] + k - 1];
        if (pos == n + 1)
            break;
        pos = nxt[pos][2];
        if (pos == n + 1)
            break;
        pos = path[a[pos]][cur[pos] + k - 1];
        if (pos == n + 1)
            break;

        ans = min(ans, n - 3 * k - (i - 1) - (n - pos));

    }

    if (ans == 1e9)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     while(path[0].size() < 2 * n)
      |           ~~~~~~~~~~~~~~~^~~~~~~
ho_t2.cpp:66:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     while(path[1].size() < 2 * n)
      |           ~~~~~~~~~~~~~~~^~~~~~~
ho_t2.cpp:68:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     while(path[2].size() < 2 * n)
      |           ~~~~~~~~~~~~~~~^~~~~~~
ho_t2.cpp:68:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   68 |     while(path[2].size() < 2 * n)
      |     ^~~~~
ho_t2.cpp:71:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   71 |         int ans = 1e9;
      |         ^~~
ho_t2.cpp:75:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |         if (a[pos] != 0)
      |         ^~
ho_t2.cpp:77:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |             if (pos == n + 1)
      |             ^~

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