Submission #567101

#	Time	Username	Problem	Language	Result	Execution time	Memory
567101		Belgutei	Painting Walls (APIO20_paint)	C++17	28 / 100	94 ms	16704 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


map<int,bool> mp[100005];
map<ll,bool> mm;
int dp[1005];

vector<int> v[30];
int l,r;
int mn;
int z[30];
int level;

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

void update(int pos, int val) {
    v[level][pos] = val;
    for(int i = level - 1; i >= 0; i --) {
        pos/=2;
        v[i][pos] = min(v[i + 1][pos * 2],v[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) {

    bool sub_1 = 0;
    for(int i = 0; i < B.size(); i ++) {
        if(B[i].size() > 1) sub_1 = 1;
    }
    if(sub_1 == 0) { 
        // subtask 1
        ll zereg[N + 5];
        zereg[0] = 1;
        for(int i = 1; i <= N; i ++) {
            zereg[i] = (zereg[i - 1] * 10) % MOD;
        }

        //
        ll hash_val[M + 5];
        hash_val[0] = 0;
        for(int i = 0; i < M; i ++) {
            hash_val[0] = (hash_val[0] * 10 + B[i][0]) % MOD;
        }   
        for(int i = 0; i < M; i ++) {
            hash_val[i + 1] = ((hash_val[i] - (B[i][0] * zereg[M - 1]) % MOD + MOD) % MOD * 10 + B[i][0]) % MOD;
        }
        for(int i = 0; i < M; i ++) {
            mm[hash_val[i]] = 1;
            debug(hash_val[i]);
        }
        //
        z[0] = 1;
        for(int i = 0; i < 30; i ++) {
            if(z[i] >= N) {
                level = i;
                break;
            }
            z[i + 1] = z[i] * 2;
        }
        for(int i = 0; i <= level; i ++) {
            for(int j = 0; j < z[i]; j ++) {
                v[i].pb(1e9 + 7);
            }
        }
        //
        ll h[N + 5];
        for(int i = 0; i < N; i ++) {
            if(i == 0) h[i] = C[i];
            else {
                h[i] = (h[i - 1] * 10 + C[i]) % MOD;
            }
            debug(h[i]);
        }
        //
        for(int i = M - 1; i < N; i ++) {
            ll cur_hash = h[i];
            if(i != M - 1) {
                cur_hash = (h[i] - (h[i - M] * zereg[M]) % MOD + MOD) % MOD;
            }
            debug(cur_hash);
            if(mm[cur_hash] == 1) {
                //debug("WTF");
                if(i == M - 1) {
                    update(i,1);
                    continue;
                }
                l = i - M;
                r = i - 1;
                debug(i);
                //cout << l << ' ' << r << '\n';
                mn = 1e9 + 7;
                dfs(0,0);
                update(i,mn + 1);
            }
        }
        /*
        for(int i = 0; i<= level; i ++) {
            for(int j = 0; j < v[i].size(); j ++) {
                cout << v[i][j] << ' ';
            }
            cout << '\n';
        }
        */
        if(v[level][N - 1] >= 1e9) {
            return -1;
        }
        return v[level][N - 1];
    }

    for(int i = 0; i < B.size(); i ++) {
        for(int j = 0; j < B[i].size(); j ++) {
            mp[i][B[i][j]] = 1;
        }
    }

    for(int i = M - 1; i < N; i ++) {
        int l = i - M + 1;
        int r = i;
        int starter = 0;
        bool check = 0;
        while(starter < M) {
            int cur = starter;
            bool ok = 0;
            for(int j = l; j <= r; j ++) {
                if(mp[cur][C[j]] == 0) {
                    ok = 1;
                    break;
                }
                cur ++;
                if(cur == M) cur = 0;
            }
            if(ok == 0) {
                check = 1;
                break;
            }
            starter ++;
        } 
        if(check == 0) {
            continue;
        }
        if(i == M - 1) {
            dp[i] = 1;
            continue;
        }
        int mn = 1e9;
        for(int j = i - 1; j >= i - M; j --) {
            if(dp[j] == 0) continue;
            mn = min(mn,dp[j]);
        }
        if(mn != 1e9) {
            mn ++;
            dp[i] = mn;
        }
    }
    if(dp[N - 1] == 0) return -1;
    return dp[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:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < B.size(); i ++) {
      |                    ~~^~~~~~~~~~
paint.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i = 0; i < B.size(); i ++) {
      |                    ~~^~~~~~~~~~
paint.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int j = 0; j < B[i].size(); j ++) {
      |                        ~~^~~~~~~~~~~~~

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