Submission #522591

#	Time	Username	Problem	Language	Result	Execution time	Memory
522591		maomao90	Painting Walls (APIO20_paint)	C++17	51 / 100	1549 ms	199816 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mxto(T &a, T b) {return a < b ? a = b, 1 : 0;}
template <class T>
inline bool mnto(T &a, T b) {return a > b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
#define MP make_pair
typedef pair<int, int> ii;
#define pb push_back
#define ALL(x) x.begin(), x.end()
typedef vector<int> vi;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define MAXN 100005

int n, m, k;
vi c, a;
vector<vi> b;
vi mp[MAXN];
bool p[MAXN][2005];

int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b) {
    ::n = n; ::m = m; ::k = k; ::c = c; ::a = a; ::b = b;
    REP (i, 0, m) {
        for (int j : b[i]) {
            mp[j].pb(i);
        }
    }
    REP (i, 0, n) {
        cerr << i << ":";
        for (int j : mp[c[i]]) {
            cerr << " " << j;
            p[i][((j - i) % m + m) % m] = 1;
        }
        cerr << "\n";
    }
    vi rng;
    REP (i, 0, n - m + 1) {
        REP (j, 0, m) {
            bool pos = 1;
            REP (k, i, i + m) {
                if (!p[k][j]) {
                    pos = 0;
                    break;
                }
            }
            if (pos) {
                rng.pb(i);
                cerr << i << "\n";
                break;
            }
        }
    }
    if (rng.empty() || rng[0] != 0 || rng.back() != n - m) {
        return -1;
    }
    if (rng.size() == 1) {
        return 1;
    }
    int r = m;
    int ans = 2;
    REP (i, 1, rng.size() - 1) {
        if (rng[i] > r) {
            return -1;
        }
        if (rng[i + 1] > r) {
            r = rng[i] + m;
            ans++;
        }
    }
    if (n - m > r) return -1;
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, vi, vi, std::vector<std::vector<int> >)':
paint.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   74 |     REP (i, 1, rng.size() - 1) {
      |          ~~~~~~~~~~~~~~~~~~~~           
paint.cpp:74:5: note: in expansion of macro 'REP'
   74 |     REP (i, 1, rng.size() - 1) {
      |     ^~~

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