Submission #395232

#	Time	Username	Problem	Language	Result	Execution time	Memory
395232		abc864197532	Painting Walls (APIO20_paint)	C++17	63 / 100	1605 ms	407272 KiB

paint

#include <bits/stdc++.h>
// #include "grader_paint.cpp"
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}

int minimumInstructions(int n, int m, int k,vector <int> c, vector <int> a, vector <vector <int>> b) {
    vector <int> tmp[n], pos[k];
    int cha[n];
    for (int i = 0; i < n; ++i) cha[i] = i < m ? i : cha[i - m];
    for (int i = 0; i < n; ++i) pos[c[i]].pb(i);
    for (int i = 0; i < m; ++i) {
        for (int &j : b[i]) {
            for (int &ii : pos[j]) {
                int t = ii - i;
                t = t >= 0 ? cha[t] : t + m;
                tmp[ii].pb(t);
            }
        }
    }
    int cnt[m]{}, num[m + 1]{};
    num[0] = m;
    vector <int> seg;
    for (int i = 0; i < m; ++i) {
        for (int &j : tmp[i]) {
            num[cnt[j]]--;
            cnt[j]++;
            num[cnt[j]]++;
        }
    }
    if (num[m] > 0) seg.pb(0);
    for (int i = m; i < n; ++i) {
        for (int &j : tmp[i - m]) {
            num[cnt[j]]--;
            cnt[j]--;
            num[cnt[j]]++;
        }
        for (int &j : tmp[i]) {
            num[cnt[j]]--;
            cnt[j]++;
            num[cnt[j]]++;
        }
        if (num[m] > 0) seg.pb(i - m + 1);
    }
    int ans = 0, now = 0;
    for (int i = 0; i + 1 < seg.size(); ++i) {
        if (seg[i] <= now && now < seg[i + 1]) {
            ans++;
            now = seg[i] + m;
        } else if (now < seg[i]) {
            return -1;
        }
    }
    if (!seg.empty() && seg.back() <= now) ans++, now = seg.back() + m;
    if (now != n) return -1;
    return ans;
}

/*
 8 3 5
 3 3 1 3 4 4 2 2
 3 0 1 2
 2 2 3
 2 3 4

 5 4 4
 1 0 1 2 2
 2 0 1
 1 1
 1 2
 1 3
 */

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

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