Submission #766851

#	Time	Username	Problem	Language	Result	Execution time	Memory
766851		Kihihihi	Painting Walls (APIO20_paint)	C++17	100 / 100	350 ms	505128 KiB

paint

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
#include "paint.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 20;
const long double EPS = 1e-9, PI = acos(-1);

struct quemin
{
    int l = 0, r = -1;
    deque<pair<int, int>> q;

    quemin() {}

    void push_back(int x)
    {
        while (q.size() && q.back().first >= x)
        {
            q.pop_back();
        }
        r++;
        q.push_back({ x, r });
    }

    void pop_front()
    {
        if (q.front().second == l)
        {
            q.pop_front();
        }
        l++;
    }

    int get()
    {
        return q.front().first;
    }
};

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
{
    int n = N, m = M, k = K;
    vector<int> c = C, a = A;
    vector<vector<int>> b = B;

    vector<vector<int>> like(k);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < b[i].size(); j++)
        {
            like[b[i][j]].push_back(i);
        }
    }

    vector<vector<int>> has(n);
    for (int i = 0; i < n; i++)
    {
        has[i] = like[c[i]];
    }

    vector<vector<int>> tomx(n);
    vector<pair<int, int>> nxt(m, { -1, -1 });
    vector<int> pos0(n, -1);
    for (int i = n - 1; i > -1; i--)
    {
        tomx[i].resize(has[i].size());
        for (int j = 0; j < has[i].size(); j++)
        {
            tomx[i][j] = has[i][j];
            if (has[i][j] == m - 1)
            {
                continue;
            }

            if (nxt[has[i][j] + 1].first == i + 1)
            {
                tomx[i][j] = tomx[nxt[has[i][j] + 1].first][nxt[has[i][j] + 1].second];
            }
        }

        for (int j = 0; j < has[i].size(); j++)
        {
            if (has[i][j] == 0)
            {
                pos0[i] = j;
            }

            nxt[has[i][j]] = { i, j };
        }
    }

    vector<bool> can(n);
    for (int i = n - m; i > -1; i--)
    {
        for (int j = 0; j < has[i].size(); j++)
        {
            if (tomx[i][j] != m - 1)
            {
                continue;
            }
            
            if (has[i][j] != 0)
            {
                int to = i + (m - has[i][j]);
                if (pos0[to] == -1)
                {
                    continue;
                }
                if (tomx[to][pos0[to]] < has[i][j] - 1)
                {
                    continue;
                }
            }

            can[i] = true;
            break;
        }
    }

    vector<int> dp(n + 1, INF);
    dp[n] = 0;
    quemin qmn;
    for (int i = 0; i < m; i++)
    {
        qmn.push_back(dp[n - i]);
    }
    for (int i = n - m; i > -1; i--)
    {
        if (can[i] && qmn.get() != INF)
        {
            dp[i] = 1 + qmn.get();
        }
        
        qmn.pop_front();
        qmn.push_back(dp[i]);
    }

    return (dp[0] == INF ? -1 : dp[0]);
}

/*
int main()
{
    int N, M, K;
    assert(3 == scanf("%d %d %d", &N, &M, &K));

    std::vector<int> C(N);
    for (int i = 0; i < N; ++i)
    {
        assert(1 == scanf("%d", &C[i]));
    }

    std::vector<int> A(M);
    std::vector<std::vector<int>> B(M);
    for (int i = 0; i < M; ++i)
    {
        assert(1 == scanf("%d", &A[i]));
        B[i].resize(A[i]);
        for (int j = 0; j < A[i]; ++j)
        {
            assert(1 == scanf("%d", &B[i][j]));
        }
    }

    int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
    printf("%d\n", minimum_instructions);

    return 0;
}
*/

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int j = 0; j < b[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
paint.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int j = 0; j < has[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
paint.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int j = 0; j < has[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
paint.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j = 0; j < has[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37