Submission #651453

#	Time	Username	Problem	Language	Result	Execution time	Memory
651453		perchuts	벽 칠하기 (APIO20_paint)	C++17	100 / 100	925 ms	14464 KiB

paint

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #include "paint.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<int>f[maxn];

int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
    vector<int>w(M);
    vector<bool>pode(N);

    for(int i=0;i<M;++i){
        for(auto x : B[i]){
            f[x].pb(i);
        }
    }

    int qntM = 0, shift = 0;

    for(int i=0;i<N;++i){
        if(i>=M){
            for(auto x:f[C[i-M]]){
                int idx = (x+shift)%M;
                if(w[idx]==M)--qntM;
                w[idx]--;
            }
        }
        for(auto x:f[C[i]]){
            int idx = (x+shift)%M;
            w[idx]++;
            if(w[idx]==M)++qntM;
        }
        if(shift==0)shift = M;
        pode[i] = (qntM!=0), shift--;
    }

    int ans = 1, ptr = N-2, current = N-1;

    while(true){
        if(ans>N)break;
        int nxt = -1;

        while(ptr>-1&&ptr>=current-M){
            if(pode[ptr])nxt = ptr;
            ptr--;
        }

        if(pode[current]&&current<M)break;        

        if(nxt==-1||pode[current]==0){
            ans = -1;break;
        }

        current = nxt, ++ans;        
    }

    return ans;
}

// int main() {
//   int N, M, K;
//   assert(3 == scanf("%d %d %d", &N, &M, &K));
  
//   std::vector<int> C(N);
//   for (int i = 0; i < N; ++i) {
//     assert(1 == scanf("%d", &C[i]));
//   }

//   std::vector<int> A(M);
//   std::vector<std::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;
// }

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