Submission #919411

#	Time	Username	Problem	Language	Result	Execution time	Memory
919411		hariaakas646	Painting Walls (APIO20_paint)	C++17	100 / 100	855 ms	408992 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, l, r) for(int i=l; i<r; i++)
#define frange(i, l) forr(i, 0, l)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef long long lli;
typedef vector<vi> vvi;
typedef vector<lli> vll;
typedef vector<bool> vb;
typedef set<int> seti;
typedef multiset<int> mseti;

int minimumInstructions(
    int n, int m, int k, vector<int> col,
    vector<int> cnt, vector<std::vector<int>> fav) {

    // vector<vb> favb(m, vb(k));
    if(k <= 1e4) {vector<vector<short>> val(k);
    
        frange(i, fav.size()) {
            for(auto e : fav[i]) {
                val[e].pb(i);
            }
        }
    
    
        vector<vector<short>> dp1(n), dp2(n);
        if(val[col[0]].size() >= 1 && val[col[0]][0] == 0) dp1[0].pb(0);
    
        forr(i, 1, n) {
            int id = 0;
            while(id < val[col[i]].size() && val[col[i]][id] < 0) id++;
            if(id < val[col[i]].size() && val[col[i]][id] == 0) dp1[i].pb(0);
            for(auto e : dp1[i-1]) {
                while(id < val[col[i]].size() && val[col[i]][id] < e+1) id++;
                if(id < val[col[i]].size() && val[col[i]][id] == e+1) dp1[i].pb(e+1);
            }
        }
    
        if(val[col[n-1]].size() && val[col[n-1]].back() == m-1) dp2[n-1].pb(m-1);
    
        for(int i=n-2; i>=0; i--) {
            int id = 0;
            for(auto e : dp2[i+1]) {
                while(id < val[col[i]].size() && val[col[i]][id] < e-1) id++;
                if(id < val[col[i]].size() && val[col[i]][id] == e-1) dp2[i].pb(e-1);
            }
            while(id < val[col[i]].size() && val[col[i]][id] < m-1) id++;
            if(id < val[col[i]].size() && val[col[i]][id] == m-1) dp2[i].pb(m-1);
        }
    
        vb pos(n);
    
        forr(i, m-1, n) {
            int id = 0;
            for(auto e : dp1[i]) {
                while(id < dp2[i-m+1].size() && dp2[i-m+1][id] < e+1) id++;
                if(id < dp2[i-m+1].size() && dp2[i-m+1][id] == e+1) pos[i] = true;
            }
            
            if(dp1[i].size() && dp1[i].back() == m-1) pos[i] = true;
            if(dp2[i-m+1].size() && dp2[i-m+1].front() == 0) pos[i] = true;
        }
    
        vi dp(n, 1e9);
    
        if(pos[m-1]) dp[m-1] = 1;
    
        deque<int> dq;
        dq.pb(m-1);
    
        forr(i, m, n) {
            while(dq.size() && dq.front() < i-m) dq.pop_front();
            if(pos[i]) {
                if(dq.size())
                    dp[i] = min(dp[i], dp[dq.front()]+1);
                while(dq.size() && dp[dq.back()] >= dp[i]) dq.pop_back();
                dq.pb(i);
            }
        }
        if(dp[n-1] >= 1e9) return -1;
        else return dp[n-1];}
    else {vector<vector<int>> val(k);
    
        frange(i, fav.size()) {
            for(auto e : fav[i]) {
                val[e].pb(i);
            }
        }
    
    
        vector<vector<int>> dp1(n), dp2(n);
        if(val[col[0]].size() >= 1 && val[col[0]][0] == 0) dp1[0].pb(0);
    
        forr(i, 1, n) {
            int id = 0;
            while(id < val[col[i]].size() && val[col[i]][id] < 0) id++;
            if(id < val[col[i]].size() && val[col[i]][id] == 0) dp1[i].pb(0);
            for(auto e : dp1[i-1]) {
                while(id < val[col[i]].size() && val[col[i]][id] < e+1) id++;
                if(id < val[col[i]].size() && val[col[i]][id] == e+1) dp1[i].pb(e+1);
            }
        }
    
        if(val[col[n-1]].size() && val[col[n-1]].back() == m-1) dp2[n-1].pb(m-1);
    
        for(int i=n-2; i>=0; i--) {
            int id = 0;
            for(auto e : dp2[i+1]) {
                while(id < val[col[i]].size() && val[col[i]][id] < e-1) id++;
                if(id < val[col[i]].size() && val[col[i]][id] == e-1) dp2[i].pb(e-1);
            }
            while(id < val[col[i]].size() && val[col[i]][id] < m-1) id++;
            if(id < val[col[i]].size() && val[col[i]][id] == m-1) dp2[i].pb(m-1);
        }
    
        vb pos(n);
    
        forr(i, m-1, n) {
            int id = 0;
            for(auto e : dp1[i]) {
                while(id < dp2[i-m+1].size() && dp2[i-m+1][id] < e+1) id++;
                if(id < dp2[i-m+1].size() && dp2[i-m+1][id] == e+1) pos[i] = true;
            }
            
            if(dp1[i].size() && dp1[i].back() == m-1) pos[i] = true;
            if(dp2[i-m+1].size() && dp2[i-m+1].front() == 0) pos[i] = true;
        }
    
        vi dp(n, 1e9);
    
        if(pos[m-1]) dp[m-1] = 1;
    
        deque<int> dq;
        dq.pb(m-1);
    
        forr(i, m, n) {
            while(dq.size() && dq.front() < i-m) dq.pop_front();
            if(pos[i]) {
                if(dq.size())
                    dp[i] = min(dp[i], dp[dq.front()]+1);
                while(dq.size() && dp[dq.back()] >= dp[i]) dq.pop_back();
                dq.pb(i);
            }
        }
        if(dp[n-1] >= 1e9) return -1;
        else 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:8:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define forr(i, l, r) for(int i=l; i<r; i++)
      |                                     ^
paint.cpp:9:22: note: in expansion of macro 'forr'
    9 | #define frange(i, l) forr(i, 0, l)
      |                      ^~~~
paint.cpp:33:9: note: in expansion of macro 'frange'
   33 |         frange(i, fav.size()) {
      |         ^~~~~~
paint.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while(id < val[col[i]].size() && val[col[i]][id] < 0) id++;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             if(id < val[col[i]].size() && val[col[i]][id] == 0) dp1[i].pb(0);
      |                ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 while(id < val[col[i]].size() && val[col[i]][id] < e+1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 if(id < val[col[i]].size() && val[col[i]][id] == e+1) dp1[i].pb(e+1);
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 while(id < val[col[i]].size() && val[col[i]][id] < e-1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 if(id < val[col[i]].size() && val[col[i]][id] == e-1) dp2[i].pb(e-1);
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             while(id < val[col[i]].size() && val[col[i]][id] < m-1) id++;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if(id < val[col[i]].size() && val[col[i]][id] == m-1) dp2[i].pb(m-1);
      |                ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 while(id < dp2[i-m+1].size() && dp2[i-m+1][id] < e+1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 if(id < dp2[i-m+1].size() && dp2[i-m+1][id] == e+1) pos[i] = true;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:8:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define forr(i, l, r) for(int i=l; i<r; i++)
      |                                     ^
paint.cpp:9:22: note: in expansion of macro 'forr'
    9 | #define frange(i, l) forr(i, 0, l)
      |                      ^~~~
paint.cpp:98:9: note: in expansion of macro 'frange'
   98 |         frange(i, fav.size()) {
      |         ^~~~~~
paint.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             while(id < val[col[i]].size() && val[col[i]][id] < 0) id++;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             if(id < val[col[i]].size() && val[col[i]][id] == 0) dp1[i].pb(0);
      |                ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 while(id < val[col[i]].size() && val[col[i]][id] < e+1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 if(id < val[col[i]].size() && val[col[i]][id] == e+1) dp1[i].pb(e+1);
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 while(id < val[col[i]].size() && val[col[i]][id] < e-1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |                 if(id < val[col[i]].size() && val[col[i]][id] == e-1) dp2[i].pb(e-1);
      |                    ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             while(id < val[col[i]].size() && val[col[i]][id] < m-1) id++;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             if(id < val[col[i]].size() && val[col[i]][id] == m-1) dp2[i].pb(m-1);
      |                ~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 while(id < dp2[i-m+1].size() && dp2[i-m+1][id] < e+1) id++;
      |                       ~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                 if(id < dp2[i-m+1].size() && dp2[i-m+1][id] == e+1) pos[i] = true;
      |                    ~~~^~~~~~~~~~~~~~~~~~~

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