Submission #740032

#	Time	Username	Problem	Language	Result	Execution time	Memory
740032		becaido	Painting Walls (APIO20_paint)	C++17	100 / 100	1247 ms	18828 KiB

paint

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "paint.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, m, k, ans;
int a[SIZE];
vector<int> v[SIZE], p[SIZE];
bool valid[SIZE];
int mx, cnt[SIZE], bnt[SIZE], dp[SIZE];

void add(int x) {
    debug("add", x);
    bnt[cnt[x]]--;
    cnt[x]++;
    bnt[cnt[x]]++;
    mx = max(mx, cnt[x]);
}
void del(int x) {
    debug("del", x);
    bnt[cnt[x]]--;
    if (mx == cnt[x] && bnt[cnt[x]] == 0) mx--;
    cnt[x]--;
    bnt[cnt[x]]++;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    n = N, m = M, k = K;
    FOR (i, 1, n) a[i] = C[i - 1] + 1;
    FOR (i, 1, m) {
        v[i] = B[i - 1];
        for (int &x : v[i]) {
            x++;
            p[x].pb(i);
        }
    }
    FOR (i, 1, n) if (p[a[i]].size() == 0) return -1;
    bnt[0] = k;
    FOR (i, 1, n) {
        for (int pos : p[a[i]]) {
            pos -= i;
            pos %= m;
            if (pos <= 0) pos += m;
            add(pos);
        }
        if (i > m) {
            for (int pos : p[a[i - m]]) {
                pos -= i - m;
                pos %= m;
                if (pos <= 0) pos += m;
                del(pos);
            }
        }
        debug(i, mx);
        if (mx == m) valid[i - m + 1] = 1;
    }
    if (!valid[1] || !valid[n - m + 1]) return debug("test"), -1;
    int cur = 0, mx = 0;
    FOR (i, 1, n) {
        if (valid[i]) debug(i), mx = i + m - 1;
        if (i > mx) return -1;
        if (i > cur) {
            ans++;
            cur = mx;
        }
    }
    return ans;
}

/*in1
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
out1
3
in2
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
out2
-1
*/

#ifdef WAIMAI
int main() {
  int N, M, K;
  assert(3 == scanf("%d %d %d", &N, &M, &K));

  vector<int> C(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &C[i]));
  }

  vector<int> A(M);
  vector<vector<int>> B(M);
  for (int i = 0; i < M; ++i) {
    assert(1 == scanf("%d", &A[i]));
    B[i].resize(A[i]);
    for (int j = 0; j < A[i]; ++j) {
      assert(1 == scanf("%d", &B[i][j]));
    }
  }

  int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
  printf("%d\n", minimum_instructions);

  return 0;
}
#endif

Compilation message (stderr)

paint.cpp: In function 'void add(int)':
paint.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
paint.cpp:35:5: note: in expansion of macro 'debug'
   35 |     debug("add", x);
      |     ^~~~~
paint.cpp: In function 'void del(int)':
paint.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
paint.cpp:42:5: note: in expansion of macro 'debug'
   42 |     debug("del", x);
      |     ^~~~~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
paint.cpp:76:9: note: in expansion of macro 'debug'
   76 |         debug(i, mx);
      |         ^~~~~
paint.cpp:16:20: warning: left operand of comma operator has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
paint.cpp:79:48: note: in expansion of macro 'debug'
   79 |     if (!valid[1] || !valid[n - m + 1]) return debug("test"), -1;
      |                                                ^~~~~
paint.cpp:16:20: warning: left operand of comma operator has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
paint.cpp:82:23: note: in expansion of macro 'debug'
   82 |         if (valid[i]) debug(i), mx = i + m - 1;
      |                       ^~~~~

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