제출 #502825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502825		Victor	벽 칠하기 (APIO20_paint)	C++17	63 / 100	1586 ms	26920 KiB

paint

    // #pragma GCC target ("avx,avx2,fma")
    // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
    // #pragma GCC optimize ("unroll-loops")
    #include "paint.h"
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define rep(i, a, b) for (int i = (a); i < (b); ++i)
    #define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
    #define trav(a, x) for (auto &a : x)
     
    #define all(x) x.begin(), x.end()
    #define sz(x) x.size()
    #define pb push_back
    #define debug(x) cout << #x << " = " << x << endl
     
    #define umap unordered_map
    #define uset unordered_set
     
    typedef pair<int, int> ii;
    typedef pair<int, ii> iii;
    typedef vector<int> vi;
    typedef vector<ii> vii;
    typedef vector<vi> vvi;
     
    typedef long long ll;
    typedef pair<ll, ll> pll;
    typedef vector<ll> vll;
    typedef vector<pll> vpll;
     
    const int INF = 1'000'000'007;
     
    
     
    int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
      int jmp_back[100005];
    uset<int> colors[100005];
    vector<bool>possible, added;
        possible.assign(N,0);
        added.resize(2*M);
        const int n=N,m=M,k=K;
     
        rep(i,0,m) trav(color,B[i]) colors[color].insert(i);
     
        for(int pos=m-1;pos<n;pos+=m) {
            int cur_color=C[pos];
     
            trav(person,colors[cur_color]) {
                int first_person=(person+1)%m,num_match=0;
                int start_pos=pos-m+1;
                rep(i,0,m-1) {
                    added[i]=colors[C[start_pos+i]].count((first_person+i)%m);
                    num_match+=added[i];
                }
     
                rep(i,m-1,m-1+min(m,(n-pos))){
                    added[i]=colors[C[start_pos+m-1]].count((first_person-1+m)%m);
                    num_match+=added[i];
                    if(num_match==m) possible[start_pos]=1;
                    
                    num_match-=added[i-m+1];
                    first_person=(first_person+1)%m;
                    ++start_pos;
                }
            }
        }
     
        int val=-INF;
        rep(i,0,n) {
            if(possible[i])val=i;
            jmp_back[i]=val;
        }
        
        int pos=0,ans=0;
        while(pos<n) {
            int nxt_pos=jmp_back[pos];
            if(nxt_pos+m>pos) {
                pos=nxt_pos+m;
                ++ans;
     
            } else return -1;
        }
        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;
    }*/

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:43:27: warning: unused variable 'k' [-Wunused-variable]
   43 |         const int n=N,m=M,k=K;
      |                           ^

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