Submission #567295

#	Time	Username	Problem	Language	Result	Execution time	Memory
567295		Belgutei	Painting Walls (APIO20_paint)	C++17	100 / 100	451 ms	15900 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define X real()
#define Y imag()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

vector<int> v[100005];

int cnt[100005];
 
int level,zereg[30];
vector<int> a[30];
int l,r;
int mn;


void dfs(int k, int x) {
    int y = zereg[level-k] * x;
    int z = zereg[level-k] * (x + 1) - 1;
    if(l <= y && z <= r) {
        mn = min(mn,a[k][x]);
        return;
    }
    if(z < l || y > r || k == level) return;
    dfs(k + 1, x * 2);
    dfs(k + 1, x * 2 + 1);
}

void update(int pos, int val) {
    a[level][pos] = val;
    for(int i = level - 1; i >= 0; i --) {
        pos /= 2;
        a[i][pos] = min(a[i + 1][pos * 2],a[i + 1][pos * 2 + 1]);
    }
}

int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    for(int i = 0; i < M; i ++) {
        for(int j = 0; j < B[i].size(); j ++) {
            // i-th person likes to paint color B[i][j]
            v[B[i][j]].pb(i);
        }
    }
    //
    zereg[0] = 1;
    for(int i = 0; i <= 30; i ++) {
        if(zereg[i] >= N) {
            level = i;
            break;
        }
        zereg[i + 1] = zereg[i] * 2;
    }
    for(int i = 0; i <= level; i ++) {
        for(int j = 0; j < zereg[i]; j ++) {
            a[i].pb(1e9);
        }
    }

    bool b[3][M + 5];
    int pos = 0;
    int next;
    //
    for(int i = 0; i < N; i ++) {
        bool check = 0;
        int tur;
        if(b[pos][M - 1] == 1) tur = cnt[M - 1];
        else tur = 0;
        //
        next = pos + 1;
        if(next == 3) next = 0;
        //
        for(int j = v[C[i]].size() - 1; j >= 0; j --) {
            int x = v[C[i]][j];
            int pre = x - 1;
            if(pre != - 1) {
                if(b[pos][pre] == 1) {
                    cnt[x] = cnt[pre] + 1;
                    if(cnt[x] >= M) cnt[x] = M; 
                }
                else cnt[x] = 1;
                if(cnt[x] == M) check = 1;
                b[next][x] = 1;
            }
            else {
                pre = M - 1;
                cnt[x] = tur + 1;
                if(cnt[x] >= M) cnt[x] = M;
                if(cnt[x] == M) check = 1;
                b[next][x] = 1;
            }
        }
        if(pos == 1) memset(b[0],0,sizeof(b[0]));
        if(pos == 2) memset(b[1],0,sizeof(b[1]));
        if(pos == 0) memset(b[2],0,sizeof(b[2]));
        pos = next;
        if(check == 1) {
            if(i == M - 1) {
                update(i,1);
                continue;
            }
            l = i - M;
            r = i - 1;
            mn = 1e9;
            dfs(0,0);
            update(i,mn + 1);
        }
    }
    if(a[level][N - 1] >= 1e9) return -1;
    return a[level][N - 1];
}

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:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j = 0; j < B[i].size(); j ++) {
      |                        ~~^~~~~~~~~~~~~

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