Submission #522666

#	Time	Username	Problem	Language	Result	Execution time	Memory
522666		maomao90	Painting Walls (APIO20_paint)	C++17	100 / 100	587 ms	18176 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
#define INF 1000000005

int n, m, k;
vi c, a;
vector<vi> b;
vi mp[MAXN];
int lst[MAXN], len[MAXN];

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, m) {
        lst[i] = -1;
    }
    vi rng;
    REP (i, 0, n) {
        int mx = -INF;
        cerr << i << "\n";
        for (int j : mp[c[i]]) {
            int k = (j - i) % m;
            if (k < 0) {
                k += m;
            }
            if (lst[k] + 1 == i) {
                len[k]++;
            } else {
                len[k] = 1;
            }
            mxto(mx, len[k]);
            lst[k] = i;
            cerr << " " << k << ": " << len[k] << "\n";
        }
        if (mx >= m) {
            rng.pb(i - m + 1);
        }
    }
    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++)
......
   75 |     REP (i, 1, rng.size() - 1) {
      |          ~~~~~~~~~~~~~~~~~~~~           
paint.cpp:75:5: note: in expansion of macro 'REP'
   75 |     REP (i, 1, rng.size() - 1) {
      |     ^~~

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