제출 #1132220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132220		t9unkubj	Painting Walls (APIO20_paint)	C++20	100 / 100	275 ms	19012 KiB

paint

#ifdef t9unkubj

#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
int min_cost(vc<int>ok,int m){
    if(!ok[0])return -1;
    int L=ok.size()-1;
    set<int>st;
    rep(i,ok.size())if(ok[i])st.insert(i);
    int ans=1;
    int now=0;
    while(now!=L){
        auto it=st.upper_bound(now+m);
        if(it==st.begin())return -1;
        it=prev(it);
        if(*it<=now)return -1;
        now=*it;
        ++ans;
    }
    return ans;
}
int min_cost_brute(vc<int>ok,int m){
    if(!ok[0])return -1;
    int L=ok.size()-1;
    vc<int>dp(ok.size(),1e9);
    dp[0]=1;
    rep(i,L){
        REP(j,1,m+1){
            if(i+j<=L&&ok[i+j])chmin(dp[i+j],dp[i]+1);
        }
    }
    if(dp.back()>1e8)return -1;
    return dp.back();
}
vc<int> brute(int n,int m,int k,vc<int>c,vc<int>a,vvc<int>b){
    vc<int>ok(n-m+1);
    rep(i,n-m+1){
        rep(j,m){
            int ok2=1;
            REP(k,i,i+m){
                int ok1=0;
                for(auto&x:b[(j+(k-i))%m]){
                    if(x==c[k]){
                        ok1=1;
                    }
                }
                ok2&=ok1;
            }
            ok[i]|=ok2;
        }
    }
    return ok;
}
vc<int> solve(int n,int m,int k,vc<int>c,vc<int>a,vvc<int>b){
    vvc<int>cols(k);
    rep(i,m){
        for(auto&x:b[i]){
            cols[x].push_back(i);
        }
    }

    vc<int>ok_cnt((n+m)*5);

    vc<int>ok(n-m+1);
    int yoi=0;
    int OFFSET=m*2;
    auto F=[&](int i,int coef){
        for(auto&x:cols[c[i]]){
            if(coef==1){
            ok_cnt[(i-x)+OFFSET]++;
            if(ok_cnt[(i-x)+OFFSET]==m){
                yoi++;
            }
            ok_cnt[(i-x)-m+OFFSET]++;
            if(ok_cnt[(i-x)-m+OFFSET]==m){
                yoi++;
            }
            }else{
            if(ok_cnt[(i-x)+OFFSET]==m){
                yoi--;
            }
            ok_cnt[(i-x)+OFFSET]--;
            if(ok_cnt[(i-x)-m+OFFSET]==m){
                yoi--;
            }
            
            ok_cnt[(i-x)-m+OFFSET]--;
            }
        }
    };
    rep(i,m){
        F(i,1);
    }
    ok[0]=!!yoi;
    REP(i,m,n){
        F(i-m,-1);
        F(i,1);
        //dbg(i,ok_cnt);
        ok[i-m+1]=!!yoi;
    }
    return ok;
    
}
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
        dbg(solve(N,M,K,C,A,B));
  return min_cost(solve(N,M,K,C,A,B),M);
}
namespace judge{
    void run(){
        #ifdef t9unkubj
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif
        int n,m,k;
        cin>>n>>m>>k;
        vc<int>c(n);
        rep(i,n)cin>>c[i];
        vc<int>a(m);
        vvc<int>b(m);
        rep(i,m){
            cin>>a[i];
            b[i].resize(a[i]);
            rep(j,a[i])cin>>b[i][j];
        }
        dbg(minimumInstructions(n,m,k,c,a,b));
    }
    void ch(){
        mt19937 mt;
        while(1){
            int n=5,m=mt()%n,k=n;
            vc<int>c(n);
            rep(i,n)c[i]=mt()%k;
            vc<int>a(m);
            vvc<int>b(m);
            rep(i,m)a[i]=mt()%3;
            rep(i,m){
                b[i].resize(a[i]);
                for(auto&x:b[i])x=mt()%k;
                sort(all(b[i]));
                b[i].erase(unique(all(b[i])),b[i].end());
                a[i]=b[i].size();
            }
            if(brute(n,m,k,c,a,b)!=solve(n,m,k,c,a,b)){
                dbg(n,m,k,c,a,b);
                dbg(brute(n,m,k,c,a,b));
                dbg(solve(n,m,k,c,a,b));
                assert(0);
            }
        }
    }
    void ch2(){
        mt19937 mt;
        while(1){
            int n=5,m=mt()%n;
            vc<int>ok(n);
            rep(i,n)ok[i]=mt()%2;
            if(min_cost(ok,m)!=min_cost_brute(ok,m)){
                dbg(ok,m);
                dbg(min_cost(ok,m));
                dbg(min_cost_brute(ok,m));
                assert(0);
            }
        }
    }
};
//int main(){judge::run();}
//g++ paint.cpp -D t9unkubj
/*
8
1 0 1 0 1 1 1 1
3
*/

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